KMP

#include <stdio.h>
#include <stdlib.h>
#include<map>
#include<algorithm>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100010;
int nex[maxn];
void getnex(char *p)
{
    int len=strlen(p);
    int i=0,j=-1;
    nex[0]=-1;
    while(i<len){
        while(j!=-1&&p[i]!=p[j]){
            j=nex[j];
        }
        nex[++i]=++j;
    }
}
void KMP(char *s,char *p)
{
    getnex(p);
    int len1=strlen(s);
    int len2=strlen(p);
    int i=0,j=0;
    while(i<len1){
        while(j!=-1&&s[i]!=p[j]){
            j=nex[j];
        }
        ++i;
        ++j;
        if(j==len2){
            cout<<i-len2+1<<endl;
            return ;
        }
    }
    cout<<-1<<endl;
}
int main()
{
//    char s1[100],s2[100];
//    while(cin>>s1>>s2)KMP(s1,s2);
    return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include<map>
#include<algorithm>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100010;
int nex[maxn];
void getnex(char *p)
{
    int len=strlen(p);
    int i=0,j=-1;
    nex[0]=-1;
    while(i<len){
        while(j!=-1&&p[i]!=p[j]){
            j=nex[j];
        }
        nex[++i]=++j;
    }
}
void KMP(char *s,char *p)
{
    getnex(p);
    int len1=strlen(s);
    int len2=strlen(p);
    int i=0,j=0;
    while(i<len1){
        while(j!=-1&&s[i]!=p[j]){
            j=nex[j];
        }
        ++i;
        ++j;
        if(j==len2){
            cout<<i-len2+1<<endl;
            return ;
        }
    }
    cout<<-1<<endl;
}
int main()
{
    char s1[100],s2[100];
    while(cin>>s1>>s2)KMP(s1,s2);
    return 0;
}

 

上一篇:[bzoj1143]祭祀


下一篇:Windows入侵排查思路