HDU 1867 A + B for you again

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1867

题目大概意思就是有重复的就覆盖掉然后输出。不过这个得比较字符串str1 str2还得再比较str2 str1.

思路 KMP算法掌握的还是不熟。

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #define N 100001
 5  int nextt[N];
 6  void next(char s[])
 7  {
 8      int i=1,j=0;
 9      int len=strlen(s);
10      nextt[0]=-1;
11      while(i<len)
12      {
13          if(j==-1||s[i]==s[j])
14          {
15              ++i;
16              ++j;
17              if(s[i]!=s[j])
18                  nextt[i]=j;
19              else
20                  nextt[i]=nextt[j];
21          }
22          else
23              j=nextt[j];
24      }
25  }
26  int kmp(char ss[],char s[])
27  {
28      int len1=strlen(ss);
29      int len2=strlen(s);
30      next(s);
31      int i=0,j=0;
32      while(i<len1&&j<len2)
33      {
34          if(j==-1||ss[i]==s[j])
35          {
36              ++i;
37              ++j;
38          }
39          else
40              j=nextt[j];
41      }
42      if(i==len1)
43          return j;
44      return 0;
45  }
46  int main()
47  {
48      char str1[N],str2[N];
49      while(~scanf("%s%s",str1,str2))
50      {
51          int x=kmp(str1,str2);
52          int y=kmp(str2,str1);
53          if(x==y)
54          {
55              if(strcmp(str1,str2)>0)
56              {
57                  printf("%s",str2);
58                  printf("%s\n",str1+x);
59              }
60              else
61              {
62                  printf("%s",str1);
63                  printf("%s\n",str2+x);
64              }
65          }
66          else if(x>y)
67          {
68              printf("%s",str1);
69              printf("%s\n",str2+x);
70          }
71          else
72          {
73              printf("%s",str2);
74              printf("%s\n",str1+y);
75          }
76      }
77      return 0;
78  }