Kolya and Tandem Repeat

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Kolya got string s for his birthday, the string consists of small English letters. He immediately added k more characters to the right of the string.

Then Borya came and said that the new string contained a tandem repeat of length l as a substring. How large could l be?

See notes for definition of a tandem repeat.

Input

The first line contains s (1 ≤ |s| ≤ 200). This string contains only small English letters. The second line contains number k (1 ≤ k ≤ 200) — the number of the added characters.

Output

Print a single number — the maximum length of the tandem repeat that could have occurred in the new string.

Sample test(s)

Input

aaba2

Output

6

Input

aaabbbb2

Output

6

Input

abracadabra10

Output

20

Note

A tandem repeat of length 2n is string s, where for any position i (1 ≤ i ≤ n) the following condition fulfills: s_i = s_i + n.

In the first sample Kolya could obtain a string aabaab, in the second — aaabbbbbb, in the third — abracadabrabracadabra

题意：给定一个字符串和一个数，k为可添加的字符数，求反复两次的最大字符串长度。

思路：暴力也能过，也可用hash进行优化。搜索，假设都在给定字符串内，推断同样，假设后面前短点在给定字符串里面，推断此端点到字符串结尾与前面相应的是否匹配。假设反复的那个都在补的里面。则不用推断。

AC代码：

import java.util.*;public class Main {    static int hash[]=new int[210];    static int f[]=new int[210];    static boolean check(int x1,int y1,int x2,int y2){        return hash[y1]-hash[x1-1]*f[y1-x1+1]==hash[y2]-hash[x2-1]*f[y2-x2+1];    }    public static void main(String[] args) {        Scanner scan=new Scanner(System.in);        String s=scan.nextLine();        int k=scan.nextInt();        f[0]=1;        char a[]=new char[s.length()];        a=s.toCharArray();        int len=s.length();        for(int i=1;i<=len;i++){            hash[i]=hash[i-1]*111111+a[i-1];            f[i]=f[i-1]*111111;        }        int ans=0;        for(int i=1;i<=len+k;i++){            for(int j=i;j<=len+k;j++){                int x1=i,y1=j,x2=j+1,y2=j+j-i+1;                if(y2>len+k) break;                if(y2<=len){                    if(check(x1,y1,x2,y2))                        ans=Math.max(ans, y2-x1+1);                }                else if(x2<=len){                    if(check(x1,x1+len-x2,x2,len))                        ans=Math.max(ans, y2-x1+1);                }                else                    ans=Math.max(ans,y2-x1+1);            }        }        System.out.println(ans);    }}