//#define LOCAL
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXN 250000+10
int N;
char str1[MAXN], str2[MAXN];
char temp[MAXN*2];
int kmp(char* s, char* t, int pos);
void get_next(char* t, int* next, int t_len);
int main()
{
#ifdef LOCAL
freopen("1423_String_Tale_2.in", "r", stdin);
freopen("1423_String_Tale_2.out", "w", stdout);
#endif
scanf("%d", &N);
scanf("%s%s", str1, str2);
int s1_len = strlen(str1);
int s2_len = strlen(str2);
if(s1_len != s2_len){
printf("%d\n", -1);
return 0;
}
strcpy(temp, str1);
strcat(temp, str1);
int ans;
ans = kmp(temp, str2, 0);
if(ans != 0 && ans != -1)
printf("%d\n", s1_len-ans);
else
printf("%d\n", ans);
return 0;
}
int kmp(char* s, char* t, int pos)
{
int s_len = strlen(s);
if(pos<0 || pos>s_len-1){
fprintf(stderr, "%s", "Error: invalid pos.");
system("pause");
}
int t_len = strlen(t);
int *next = (int*)malloc(sizeof(int) * t_len);
get_next(t, next, t_len);
int i = pos;
int j = 0;
while(i<s_len && j<t_len){
if(j<0 || s[i]==t[j]){
i++;
j++;
}
else
j = next[j];
}
// free(next);
if(j >= t_len)
return i-t_len;
else
return -1;
}
void get_next(char* t, int* next, int t_len)
{
next[0] = -1;
int j = 0;
int k = -1;
while(j < t_len){
if(k==-1 || t[j]==t[k]){
j++;
k++;
next[j] = k;
}
else
k = next[k];
}
}
###############################################
Can anyone tell me WHY???
Edited by author 11.07.2017 19:31