asp.net 如何设置网站首页/网站流量排行
题目描述：
给出两个字符串 s1 和 s2，若 s1 的区间 [l,r] 子串与 s2 完全相同，则称 s2 在 s1 中出现了，其出现位置为 l。
现在请你求出 s2 在 s1 中所有出现的位置。
定义一个字符串 s 的 border 为 s 的一个非s本身的子串 t，满足 t 既是 s 的前缀，又是 s 的后缀。
对于 s2，你还需要求出对于其每个前缀 s′ 的最长 border t′ 的长度。
输入： 第一行为一个字符串，即为 s1；第二行为一个字符串，即为 s2。
输出：首先输出若干行，每行一个整数，按照从大到小顺序出 s_2s2 在 s_1s1 中出现的位置。
最后一行输出 ∣s2∣ 个整数，第 i 个整数表示 s2 的长度为 i 的前缀的最长 border 长度。
解题思路：
1、属于模式匹配KMP算法，整体思想与《算法导论》上的KMP算法一致，但是细节不同，本题中用下标描述，《算法导论》中用的是自然序，所以要改变求解next序列的函数；而且要求出所有的匹配成功子序列，不是第一个子序列。
2、求解next序列时，把所有的参数初始值都-1，再改变while循环中的上界，确保不会出界即可；
3、在匹配函数中，遍历s1和s2均按照下标进行，初始值为0；其余不变，匹配成功都+1，不成功j回退；
4、在匹配while循环外再设置一层while循环，在匹配成功一次后，令j = go_back[j]，即可实现依次输出所有匹配成功的串的首元素下标。
代码实现：
#include <iostream>
using namespace std;
#include <string>int go_back[100 + 5];void GetGoBack(const string& s)
{int i = 0, k = -1;int len = s.size();go_back[0] = -1;while (i < len){if (k == -1 || s[i] == s[k]){go_back[++i] = ++k;}else{k = go_back[k];}}
}void KMP(const string& s1, const string& s2)
{int i = 0, j = 0;int len1 = s1.size();int len2 = s2.size();while (i < len1){while (i < len1 && j < len2){if (j == -1 || s1[i] == s2[j]){i++;j++;}else{j = go_back[j];}}if (j == len2){cout << i - len2 + 1 << endl;j = go_back[j];}}
}int main()
{string s1, s2;cin >> s1 >> s2;GetGoBack(s2);KMP(s1, s2);int len = s2.size();for (int i = 1; i <= len; i++){cout << go_back[i] << " ";}cout << endl;return 0;
}