Cod sursa(job #1327759)

Utilizator theprdvtheprdv theprdv Data 27 ianuarie 2015 05:59:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <string.h>
using namespace std;
fstream fin("strmatch.in", ios::in);
fstream fout("strmatch.out", ios::out);

#define MAX 2000010
char N[MAX], M[MAX];
int n, m, pi[MAX], d[1005];

void prefix()
{
    int q=0;
    pi[1]=0;
    for(int i=2; i<=n; i++){
        while(N[i]!=N[q+1] && q>0)
            q=pi[q];
        if(N[q+1]==N[i])
            q++;
        pi[i]=q;
    }
}
void KMP()
{
    int q=0;
    pi[1]=0;
    for(int i=2; i<=n; i++){
        while(N[i]!=N[q+1] && q>0)
            q=pi[q];
        if(N[q+1]==N[i])
            q++;
        pi[i]=q;
    }
    q=0;
    for(int i=1; i<=m; i++){
        while(N[q+1]!=M[i] && q>0)
            q=pi[q];
        if(M[i]==N[q+1])
            q++;
        if(q==n)
            d[++d[0]]=i-n;

    }
}

int main()
{
    fin.getline(N+1, MAX);    ::n=strlen(N+1);
    fin.getline(M+1, MAX);    ::m=strlen(M+1);
    KMP();
    fout<<d[0]<<"\n";
    for(int i=1; i<=d[0]; i++)
        fout<<d[i]<<" ";

    fin.close();
    fout.close();
    return 0;
}