Cod sursa(job #1364515)

Utilizator biancaiftimeIftime Bianca biancaiftime Data 27 februarie 2015 18:21:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int pi[2000000],d[1000],n,m,nr,i;
char s[2000001],t[2000001];
void Precalculare()
{
    int i,k;
    pi[0]=0; k=0;
    for(i=1;i<m;i++)
    {
        if(t[i]==t[k]) k++;
        else
        {
            while(k>0&&t[k]!=t[i]) k=pi[k-1];
            if(t[k]==t[i]) k++;
        }
        pi[i]=k;
    }
}
void KMP()
{
    int i,k=0;
    for(i=0;i<n;i++)
    {
        if(s[i]==t[k]) k++;
        else
        {
            while(k>0&&t[k]!=s[i]) k=pi[k-1];
            if(s[i]==t[k]) k++;
        }
        if(k==m) {nr++; if(nr<=1000) d[nr]=i-m+1;  }
    }
}
int main()
{
    fin>>t;
    fin>>s;
    n=strlen(s);
    m=strlen(t);
    Precalculare();
    KMP();
    fout<<nr<<"\n";
    if(nr<=1000) for(i=1;i<=nr;i++) fout<<d[i]<<" ";
    else for(i=1;i<=1000;i++) fout<<d[i]<<" ";
    return 0;
}