Cod sursa(job #1332744)

Utilizator gabib97Gabriel Boroghina gabib97 Data 2 februarie 2015 13:14:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int n,m,i,urm[2000005],d[2000001],t;
char T[2000005],P[2000005];
void prefix()
{
    int i,k=-1;
    urm[0]=0;
    for (i=1;i<m;i++)
    {
        while (k>0&&P[k+1]!=P[i]) k=urm[k];
        if (P[k+1]==P[i]) k++;
        urm[i]=k;
    }
}
void kmp()
{
    int i,k=-1;
    for (i=0;i<n;i++)
    {
        while (k>0&&P[k+1]!=T[i]) k=urm[k];
        if (P[k+1]==T[i]) k++;
        if (k==m-1) d[++t]=i-m+1;
    }
}
int main()
{
    fin.getline(P,2000001);
    fin.getline(T,2000001);
    n=strlen(T);
    m=strlen(P);
    prefix();
    kmp();
    fout<<t<<'\n';
    for (i=1;i<=min(1000,t);i++) fout<<d[i]<<" ";
    fin.close();
    fout.close();
    return 0;
}