Cod sursa(job #2359097)

Utilizator BungerNadejde George Bunger Data 28 februarie 2019 17:07:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
/// KMP
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int NMAX=2e6+5;
int LPS[NMAX],apar[NMAX],N,M;
char txt[NMAX],pat[NMAX];
void LPSCompute()
{

    LPS[0]=0;
    int i=1,j=0;

    while(i<M)
    {
        if(pat[i]==pat[j])
        {
            LPS[i]=j+1;
            j++;
            i++;
        }
        else
        {
            if(j==0) LPS[i++]=0;
            else     j=LPS[j-1];
        }
    }

}
void KMP()
{
    int i=0,j=0,num=0;
    while(i<N)
    {
        if(pat[j]==txt[i])
        {
            i++;
            j++;
        }
        if(j==M)
        {
            apar[++num]=i-j;
            j=LPS[j-1];
        }
        else if(pat[j]!=txt[i] && i<N)
        {
            if(j!=0) j=LPS[j-1];
            else     i++;
       }
    }
    fout<<num<<'\n';
    for(int k=1;k<=min(num,1000);k++) fout<<apar[k]<<" ";
}
int main()
{
    fin>>pat>>txt;
    M=strlen(pat);
    N=strlen(txt);
    LPSCompute();
    KMP();
    return 0;
}