KMP

算法1

C++ 代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10,M = 1e6 + 10;

char p[N],s[M];
int ne[M];
int n,m;

int main()
{
    cin>>n>>p + 1;
    cin>>m>>s + 1;

    //求next数组
    for(int i = 2,j = 0;i <= n;i ++)    //<=n
    {
        while(j&&p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j ++;
        ne[i] = j;
    }

    //kmp过程
    for(int i = 1,j = 0;i <= m;i ++)    //<=m
    {
        while(j && s[i] != p[j + 1]) j = ne[j];
        if(s[i] == p[j + 1]) j ++;
        if(j == n)
        {
            cout<< i - n <<" ";
            j = ne[j];  //匹配成功后向后移
        }
    }
    return 0;
}

算法2

(随机匹配)

既然暴力过不了，那就赌一赌。
思路：主串是1e6级别，第一层直接暴力，第二层随机选子串的任意位置字符与主串的对应位置字符相比较，如果多次匹配全部相等，就大胆认为子串匹配成功，要知道第二层如果匹配100次，总数量级规模最大不过1e8。本想着卡一下测试数据应该能混个AC，但是只过了12/14的数据。

C++ 代码

#include<iostream>
#include<time.h>
#include<string>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    string p,s;
    cin>>n>>p;
    cin>>m>>s;

    srand(time(NULL));
    int flag,x;
    for(int i = 0;i < s.size();i++)
    {  
        x = i,flag = 1;
        for(int j = 0;j < 70;j ++)
        { 
            int k = rand()%p.size();
            if(p[k] == s[k + x]) ;
            else 
            {    
                flag = 0;
                break;
            }
        }
        if(flag)cout<<i<<" ";
    }
    return 0;
}