Given two sequences of numbers : a[1], a[2], …… , a[N], and b[1], b[2], …… , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], …… , a[K + M - 1] = b[M]. If there are more than one K exist, output the smallest one.
Input The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], …… , a[N]. The third line contains M integers which indicate b[1], b[2], …… , b[M]. All integers are in the range of [-1000000, 1000000]. Output For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead. Sample Input 2 13 5 1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 1 3 13 5 1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 2 1 Sample Output 6 -1让求出现两次以上的包含所有的循环节，求补足循环节的最小花费
这里我们说被匹配串是A 匹配串是B next数组 是 B数组 前缀和后缀[i~m]的最大公共长度，所以后面所有的next 长度 指的都是前缀从0开始的。 所以 len-next[len] 必然是循环节长度，如果该长度len-next[len]!=0&&len%(len-next[len)==0 那么消耗就是0，如果不是完美的那么需要添加的字符数就是cir - (len-(len/cir)*cir))，相当与需要在最后一个循环节上面添加几个。 就是(循环节长度-最后已匹配的长度）%循环节长度#includeusing namespace std;const int maxn=100100 ;int f[maxn]; void getfill(char *s,int len) { memset(f,0,sizeof(f)); for(int i=1;i<=len;i++) { int j=f[i]; while(j && s[i]!=s[j]) j=f[j]; f[i+1]=(s[i]==s[j])?j+1:0; } } char s[maxn];int main(){ int t; cin>>t; while(t--) { scanf(" %s",s); int len=strlen(s); getfill(s,len); int length=len-f[len]; if(len!=length&&len%length==0) printf("0\n"); else{ int add=length-f[len]%length; printf("%d\n",add ); } } return 0;}