题目
Problem Description
如题，给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。
为了减少骗分的情况，接下来还要输出子串的前缀数组next。
（如果你不知道这是什么意思也不要问，去百度搜[kmp算法]学习一下就知道了。）
Input
第一行为一个字符串，即为s1（仅包含大写字母）
第二行为一个字符串，即为s2（仅包含大写字母）
Output
若干行，每行包含一个整数，表示s2在s1中出现的位置
接下来1行，包括length(s2)个整数，表示前缀数组next[i]的值。
Sample Input
ABABABC
ABA
Sample Output
1 3 0 0 1
题解
数据结构讲串的时候讲到了KMP算法，然后个人想写一写。同时，还有一个比KMP算法更快更简单的Sunday算法，也想写一写，然后就这么愉快的决定了。
KMP算法
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为KMP算法。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next[]数组，其本身包含了模式串的局部匹配信息。
这里给出一种非常好理解的KMP算法。KMP算法的核心就是构造失败指针，即next[]数组。因此如果next[]数组的含义足够简单，KMP算法的内核就很好理解了。我们把两种next[]数组的构造样例放在下面，然后分析那个比较容易理解的。
| 下标i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| t[i] | a | b | c | a | b | a | b | c | a | b | c |
| next'[i] | -1 | 0 | 0 | 0 | 1 | 2 | 1 | 2 | 3 | 4 | 5 |
| next[i] | 0 | 0 | 0 | 1 | 2 | 1 | 2 | 3 | 4 | 5 | 3 |
第一种方法构造出的next[]数组其实是真正的KMP算法的next[]数组，但我管感觉有点弯弯绕，不太好理解……但是第二种方法就很好理解了，next[i]表示的是，以第i位结尾，长度为next[i]的字符串与字符串t的长度为next[i]的前缀相同。例如next[9]=5，则我们知道t[5-9]与t[0-4]相同。我们可以找出规律，第一种构造出的其实就是第二种构造出的右移一位并讲next[0]赋值为-1。我们只要愉快的记住第二个数组的构造方法和使用方法就可以了。构造这个数组非常简单，代码如下：
j=0; for(i=1;i<lt;i++){ while(j>0 && t[i]!=t[j]) j=Next[j-1]; if(t[i]==t[j]) j++; Next[i]=j; }
i指针指向应该比较的那一位，j指针之前这前缀中的应该比较的那一位。
在上述代码中最重要的一句就是：
j=Next[j-1];
即如果两个指针所指向的两位不匹配，则看看j的前一位与前缀中的前几个匹配，然后比较前缀中之后的那一个。说起来比较绕，但举个例子就很明白了。比如当比较下标i=10的时候，j=5。我们知道next[9]=5，即t[5-9]与t[0-4]相同，因此我们可以尝试着去匹配t[10]与t[5]，如果匹配的话next[10]就可以愉快的等于next[9]+1。但是这是我们发现t[10]="c"，t[5]="d"，我们愉快的发现不匹配，怎么办呢？虽然不匹配，但是next[5-1]=next[4]=2，即t[3-4]与t[0-1]相同，此时便是j=Next[j-1]。于是我们又可以愉快的尝试着去匹配t[10]与t[2]，然后发现匹配上了……然后就可以愉快的赋值了。
得到的next[]数组使用起来也非常简单，代码如下：
j=0; for(i=0;i<ls;i++){ if(j==lt){ cout << i-lt+1 << endl; j=Next[j-1]; } while(j>0 && s[i]!=t[j]) j=Next[j-1]; if(s[i]==t[j]) j++; } if(j==lt) cout << i-lt+1 << endl;
理解方其实和上面是相似的。最后两行主要是防止最后一个字符串匹配无法输出的问题……
Sunday算法
我们来介绍一种更神奇的算法——Sunday算法……KMP算法我在上面叨叨了半天也不一定能有人理解，但是为了数据结构考试我不得不搞清楚令人头疼的KMP算法。抛开考试不提，Sunday算法是一个又简单又高效的算法……
Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其核心思想是：在匹配过程中，模式串发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。
对于t，我们做一个简单而巧妙的预处理：找出t中每一种字符最后出现的位置，将其存入一个数组中。我们可以使用map容器……大概是O(m)的复杂度。构造好失败指针后，进行O(n)复杂度的比较。
直接上例子，一边举例一边解说：
| s: | a | b | d | a | e | c | c | a | a | b | c |
| i | k | ||||||||||
| t: | a | b | c | ||||||||
| j |
整个程序是以指针k为主指针，首先k指向s串中的s[m]（m为t串长度）。
每次根据k的位置，我们将i指向k的前一个元素，j指向t，然后从后向前比较，为什么从后向前？比较坑的测评网站总是有一些s="aaaaaaaaab"，t="aaab"之类的数据存在……
如果s[i]和t[j]匹配的话，我们就将i和j前移，直到j指向t的头为止。不管s的子串和t匹不匹配，不匹配就不输出，匹配就输出。
然后到了最重要的一步，我们要跳了。但是无论如何跳，s[k]一定要被判断是否在下一个匹配字符串中。最好的情况是t向后移直到t的头与s[k]对齐，最坏的情况是t向后移一位，这时t的尾与s[k]对齐。既然s[k]跳不过去，我们就使t能向后移动最多位，即将t中最后一次出现s[k]的位置和s[k]对齐。我们在与处理时愉快的做了这一步。结果就是
| s: | a | b | d | a | e | c | c | a | a | b | c |
| k | |||||||||||
| t: | a | b | c | ||||||||
然后再把k指向t的后一位：
| s: | a | b | d | a | e | c | c | a | a | b | c |
| i | k | ||||||||||
| t: | a | b | c | ||||||||
| j |
然后接着比较，发现失配，然后接着移动：
| s: | a | b | d | a | e | c | c | a | a | b | c |
| i | k | ||||||||||
| t: | a | b | c | ||||||||
| j |
然后很多个表格：
| s: | a | b | d | a | e | c | c | a | a | b | c |
| i | k | ||||||||||
| t: | a | b | c | ||||||||
| j |
接着，我们发现匹配了，哈哈哈哈哈：
| s: | a | b | d | a | e | c | c | a | a | b | c |
| i | |||||||||||
| a | b | c | |||||||||
| j |
输出就行了……极度愉快极度简单极度好想的算法。
代码
KMP算法：
#include <iostream> #include <string> using namespace std; string s,t; int Next[1000005]; int main(){ int i=0,j=0,ls,lt; cin >> s >> t; ls=s.size(); lt=t.size(); j=0; for(i=1;i<lt;i++){ while(j>0 && t[i]!=t[j]) j=Next[j-1]; if(t[i]==t[j]) j++; Next[i]=j; } j=0; for(i=0;i<ls;i++){ if(j==lt){ cout << i-lt+1 << endl; j=Next[j-1]; } while(j>0 && s[i]!=t[j]) j=Next[j-1]; if(s[i]==t[j]) j++; } if(j==lt) cout << i-lt+1 << endl; for(i=0;i<lt-1;i++) cout << Next[i] << " "; cout << Next[lt-1] << endl; return 0; }
Sunday算法：
#include <iostream> #include <string> #include <map> using namespace std; string s,t; int Next[1000005]; map <char,int> f; //因为仅包含大写字母，否则的话，可以适当开大点，但我觉得不会超过100 int main(){ int i=0,j=0,k=0,ls,lt; char c; cin >> s >> t; ls=s.size(); lt=t.size();
for (i=lt-1;i>=0;i--) //构造失败指针 if(f[t[i]]==0) f[t[i]]=i+1; k=lt; while(k<=ls){ i=k-1; j=lt-1; while(j>=0 && s[i]==t[j]){ i--; j--; } if(j==-1) cout << k-lt+1 << endl; k+=lt-f[s[k]]+1; }// 其实到这里就可以结束了 j=0; for(i=1;i<lt;i++){ while(j>0 && t[i]!=t[j]) j=Next[j-1]; if(t[i]==t[j]) j++; Next[i]=j; } /*j=0; for(i=0;i<ls;i++){ if(j==lt){ cout << i-lt+1 << endl; j=Next[j-1]; } while(j>0 && s[i]!=t[j]) j=Next[j-1]; if(s[i]==t[j]) j++; } if(j==lt) cout << i-lt+1 << endl;*/ for(i=0;i<lt-1;i++) cout << Next[i] << " "; cout << Next[lt-1] << endl; return 0; }