Cod sursa(job #2417589)

Utilizator danstefanDamian Dan Stefan danstefan Data 30 aprilie 2019 14:39:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <bits/stdc++.h>
using namespace std;
int lu,j,i,v[2000010],k,n,l,ans[1010];
char s1[2000010],s2[2000010];
int main()
{
    ifstream cin ("strmatch.in");
    ofstream cout ("strmatch.out");
    cin>>s1>>s2;
    lu=strlen(s1);
    j=0;
    for(i=1; i<lu; ++i)
    {
        while(s1[i]!=s1[j]&&j>0)j=v[j-1];
        if(s1[i]==s1[j])++j,v[i]=j;
        else v[i]=0;
    }
    n=lu;
    lu=strlen(s2);
    j=0;
    for(i=0; i<lu; ++i)
    {
        while(s2[i]!=s1[j]&&j>0)j=v[j-1];
        if(s2[i]==s1[j])++j,l=j;
        else l=0;
        if(l==n)
        {
            if(k==1000)break;
            ans[++k]=i-n+1;
            l=0;
        }
    }
    cout<<k<<'\n';
    for(i=1; i<=k; ++i)cout<<ans[i]<<" ";
    return 0;
}