Cod sursa(job #1803985)

Utilizator cicero23catalin viorel cicero23 Data 12 noiembrie 2016 09:08:22
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char p[2000001],s[2000001];
int m,urm[2000003],nr,v[1005],n,t;
void prefix()
{
    int i,k=0;
    urm[1]=0;
    for(i=2;i<=m;i++)
    {
        while(k>0&&p[k]!=p[i-1])
            k=urm[k];
        if(p[k]==p[i-1])k++;
        urm[i]=k;
    }

}
void kmp()
{
    int q,k=0;
    for(q=0;q<n;q++)
    {
        while(k>0&& p[k]!=s[q])
            k=urm[k];
        if(p[k]==s[q])k++;
        if(k==m) {nr++;if(t<=1000)v[++t]=q-m+1;}
    }
}
int main()
{
    int i;
     f.getline(p,256);
     f.getline(s,2000);
     m=strlen(p);
     n=strlen(s);
     if(m>n)g<<0;
     else {

     prefix();
     kmp();
     g<<nr<<'\n';
     if(t>1000) t=1000;
     for(i=1;i<=t;i++)
        g<<v[i]<<" ";
     }
    return 0;
}