hdu 1841题目链接 题意：给两个字符串，问包含这两个字符串的最小的字符串的长度（最小是因为，一个串的子串可能是另一个串的后缀，这样出现一次就可以了）
思路：其实这道题最关键的思想部分是和kmp没有关系的。。。
我们考虑最naive的匹配方式。
如果存在文本串的子串（之前写成了后缀，特此更正，不一定是首尾拼接，这是和hdu 1867的区别）等于模式串的前缀，那么这段子串或者后缀的长度为最后的j。
两个串各做一次模式串和文本串。
不过暴力匹配复杂度爆炸，所以用了kmp。。。
upd：代码新添加了注释。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月11日 星期四 04时32分08秒
4File Name :code/hdu/r1841.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <stack>
14#include <set>
15#include <map>
16#include <string>
17#include <cmath>
18#include <cstdlib>
19#include <deque>
20#include <ctime>
21#define fst first
22#define sec second
23#define lson l,m,rt<<1
24#define rson m+1,r,rt<<1|1
25#define ms(a,x) memset(a,x,sizeof(a))
26typedef long long LL;
27#define pi pair < int ,int >
28#define MP make_pair
29
30using namespace std;
31const double eps = 1E-8;
32const int dx4[4]={1,0,0,-1};
33const int dy4[4]={0,-1,1,0};
34const int inf = 0x3f3f3f3f;
35const int N=1E6+7;
36int n;
37char a[N],b[N];
38int nxt[N];
39void getnxt(char *s)
40{
41 int i = 0;
42 int j = -1;
43 int n = strlen(s);
44 nxt[0] = -1;
45 while (i<n)
46 if (j==-1||s[i]==s[j]) nxt[++i]=++j;
47 else j = nxt[j];
48}
49int kmp(char *a,char *b)
50{
51 int n = strlen(a);
52 int m = strlen(b);
53 getnxt(b);
54 int i = 0 ;
55 int j = 0;
56 while (i<n&&j<m) //由于不一定哪个是模式串，所以要记得判边界j<m,因为这个而wa了一发
57 {
58 if (j==-1||a[i]==b[j]) i++,j++;
59 else j = nxt[j];
60 }
61
62 return j; //这道题只要求得到一个串同时包含这两个字符串，不是首尾拼接也可以，所以不用判断文本串是否为后缀（i==n)
63 return 0;
64}
65int main()
66{
67 #ifndef ONLINE_JUDGE
68 freopen("code/in.txt","r",stdin);
69 #endif
70
71 int T;
72 cin>>T;
73 while (T--)
74 {
75 scanf("%s",a);
76 scanf("%s",b);
77 int ans = kmp(a,b);
78 ans = max(ans,kmp(b,a));
79 ans = strlen(a)+strlen(b)-ans;
80 printf("%d\n",ans);
81 }
82
83
84 #ifndef ONLINE_JUDGE
85 fclose(stdin);
86 #endif
87 return 0;
88}