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

aaba
2

Output

Input

aaabbbb
2

Output

Input

abracadabra
10

Output

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);
    }

}