Cod sursa(job #1730755)

Utilizator Bodo171Bogdan Pop Bodo171 Data 17 iulie 2016 16:15:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include<fstream>
using namespace std;
string s1,s2;
int k,i,n,m,pi[2000005],cnt,rasp[1005];
ifstream f("strmatch.in");
ofstream g("strmatch.out");
void calcpref()
{
    k=-1;pi[0]=-1;
    for(i=1;i<n;i++)
    {
        while(k!=-1&&s1[i]!=s1[k+1])
            k=pi[k];
        if(s1[i]==s1[k+1]) k++;
        pi[i]=k;
    }
}
void kmp()
{
    k=-1;
    for(i=0;i<m;i++)
    {
        while(k!=-1&&s2[i]!=s1[k+1])
            k=pi[k];
        if(s1[k+1]==s2[i]) k++;

        if(k==n-1)
        {
            cnt++;
            k=pi[k];
            if(cnt<=1000)rasp[cnt]=i-n+1;
        }
    }
}
int main()
{

    f>>s1;
    f>>s2;
    n=s1.size();
    m=s2.size();
    calcpref();
    kmp();
    g<<cnt<<'\n';
    for(i=1;i<=min(1000,cnt);i++) g<<rasp[i]<<' ';
    return 0;
}