Cod sursa(job #1533169)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 22 noiembrie 2015 10:51:08
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <algorithm>
#define nmax 2000005
#include <cstring>

using namespace std;
void read();
void make_prefix();
void kmp();

char a[nmax],b[nmax];
int pi[nmax],pos[1024];
int m,n,res;

int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    read();
    make_prefix();
    kmp();
    printf("%d\n",res);
    for(int i=1;i<=min(res,1000);++i)printf("%d ",pos[i]);
    printf("\n");
    return 0;
}
void read(){
    scanf("%s ",a);m=strlen(a)-1;
    scanf("%s ",b);n=strlen(b)-1;
}
void make_prefix(){
    int i,q=0;
    for(i=2,pi[1]=0;i<=m;i++){
        while(q && a[q+1]!=a[i])q=pi[q];
        if(a[q+1]==a[i])++q;
        pi[i]=q;
    }
}
void kmp(){
    int q=0,i;
    res=0;
    for(i=1;i<=n;i++){
        while(q && a[q+1]!=b[i])q=pi[q];
        if(a[q+1]==b[i])++q;
        if(q==m){
            q=pi[m];
            ++res;
            if(res<=1000)pos[res]=i-m;
        }
    }
}