HDU 1867 KMP 求最大尾部重叠

题意：

给定2个字符串，a-b 或 b-a

尾部相同部分只输出一次

求长度最小的字符串（长度相同则字典序最小）

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; #define N 200050 int f1[N], f2[N]; char s1[N], s2[N]; void getFail(int *f, char *s){ int i, j, len = strlen(s); j = f[0] = -1; i = 0; while(i < len) { while(j!=-1 && s[i] != s[j])j = f[j]; i++, j++; if(s[i] != s[j])f[i] = j; else f[i] = f[j]; } } int KMP(int *f, char *S1, char *S2){ int pos = 0, len = strlen(S1), j = 0, i = 0; while(i <= len) { while(j!=-1 && S1[i] != S2[j]) j = f[j]; i++, j++; if(i == len)pos = max(pos, j); } return pos; } void go(char *S1, char *S2, int pos){ int i = strlen(S1); while(S2[pos]) S1[i++] = S2[pos++]; S1[i] = '\0'; } char tmp1[N], tmp2[N], as1[N], as2[N]; int main(){ while(~scanf("%s %s", s1, s2)){ getFail(f1, s1); getFail(f2, s2); int ans1 = KMP(f2, s1, s2), ans2 = KMP(f1, s2, s1); if(ans1>ans2) { go(s1, s2, ans1); printf("%s\n",s1); } else if(ans1