Cod sursa(job #2164630)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 13 martie 2018 08:51:54
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define N 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int L[N],d[N];
char T[N],P[N];
int n,m;
void Precalc()
{
    int i,k=0;
    L[0]=0;
    for(i=1;i<m;++i)
    {
        if(P[i]==P[k])k++;
        else
        {
            while(k>0 && P[i]!=P[k])k=L[k-1];
            if(P[i]==P[k])k++;
        }
        L[i]=k;
    }
}
void KMP()
{
    int i,k=0;
    for(i=0;i<n;++i)
    {
        if(T[i]==P[k])
            k++;
        else
        {
            while(k>0 && T[i]!=P[k])k=L[k-1];
            if(T[i]==P[k])k++;
        }
        d[i]=k;
    }
}
int main()
{
    int i;
    fin>>T>>P;
    n=strlen(T);
    m=strlen(P);
    Precalc();

        KMP();int ct=0;
        for(i=0;i<n;++i)if(d[i]==m)ct++;
        fout<<ct<<"\n";
        for(i=0;i<n;++i)if(d[i]==m)fout<<i-m+1<<" ";
    return 0;
}