Cod sursa(job #1207417)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 12 iulie 2014 23:13:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
//KMP
#include<fstream>
#include<cstring>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int NMAX=2000005;

char pattern[NMAX],text[NMAX];
int pi[NMAX],overlap[NMAX];
int sol[NMAX];

int main()
{
    int i,len,dr,length;
    fin>>(pattern+1);
    fin>>(text+1);
    length=strlen(pattern+1);
    pi[1]=0;
    for (i=2;i<=length;i++)
        if (pattern[i]==pattern[pi[i-1]+1])
            pi[i]=pi[i-1]+1;
        else
            {
                dr=pi[i-1];
                while (dr && pattern[dr+1]!=pattern[i]) dr=pi[dr];
                if (pattern[dr+1]==pattern[i]) pi[i]=dr+1;
            }
    len=strlen(text+1);
    for (i=1;i<=len;i++)
        {
            if (text[i]==pattern[overlap[i-1]+1])
                overlap[i]=overlap[i-1]+1;
            else
                {
                    dr=overlap[i-1];
                    while (dr && pattern[dr+1]!=text[i]) dr=pi[dr];
                    if (pattern[dr+1]==text[i]) overlap[i]=dr+1;
                }
            if (overlap[i]==length) sol[++sol[0]]=i-length;
        }
    fout<<sol[0]<<"\n";
    for (i=1;i<=min(sol[0],1000);i++) fout<<sol[i]<<" ";
    fout<<"\n";
    return 0;
}