Cod sursa(job #1524083)

Utilizator pufstarDragos Gheorghiu pufstar Data 13 noiembrie 2015 15:49:50
Problema Potrivirea sirurilor Scor 2
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <cstring>
#define MAX 2000000
using namespace std;
ifstream f("strmatch.in"); ofstream g("strmatch.out");
int U[MAX+5], n, m, sol[MAX+5], nr;
char T[MAX+5], P[MAX+5];
void Prel(char P[])
{
    int x, k=-1;
    U[0]=0;
    for(x=1; x<m; x++)
    {
        while(k>0 and P[k+1]!=P[x]) k=U[k];
        if(P[k+1]==P[x]) k++;
        U[k]=k;
    }
}
void KMP()
{
    int i, k=-1;
    for(i=0; i<n; i++)
    {
        while(k>0 and P[k+1]!=T[i]) k=U[k];
        if(P[k+1]==T[i])k++;
        if(k==m-1)
        {
            sol[++nr]=i-m+1;
            k=U[k];
        }
    }
}
int main()
{
    f.getline(P, MAX+3);
    f.getline(T, MAX+3);
    n=strlen(T);
    m=strlen(P);
    Prel(P);
    KMP();
    g<<nr<<'\n';
    for(int i=1; i<=min(nr,1000); i++) g<<sol[i]<<' ';
}