KMP算法

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
int main(void){
    int n, m;
    string p,s;
    cin>>n>>p;
    cin>>m>>s;
    vector<int>ne(n);
    ne[0]=-1;
    int j=-1;
    for(int i=1;i<n;i++){
        while(j>-1&&p[i]!=p[j+1])j=ne[j];
        if(p[i]==p[j+1])j++;
        ne[i]=j;
    }
    j=-1;
    for(int i=0;i<m;i++){
        while(j>-1&&s[i]!=p[j+1])j=ne[j];
        if(s[i]==p[j+1])j++;
        if(j==n-1){
            cout<<i-n+1<<' ';
          //  j=ne[j];
        }
    }
    return 0;
}

其中P是要查找的字符串

 

上一篇:生物信息之独孤九剑——单行perl


下一篇:Oracle 查询技巧