Cod sursa(job #2293265)

Utilizator danstefanDamian Dan Stefan danstefan Data 30 noiembrie 2018 18:44:20
Problema Potrivirea sirurilor Scor 34
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 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]=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++;
            if(nr<=1000)ans[nr]=j;
        }
    }
    cout<<nr<<'\n';
    for(i=1; i<=min(nr,1000); ++i)
        cout<<ans[i]-n+1<<" ";
    return 0;
}