Cod sursa(job #2293264)

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