Cod sursa(job #2714330)

Utilizator pachy2007Pachitanu Matei pachy2007 Data 1 martie 2021 18:12:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a,b;
int c[200000000],l,v[200000000],i,cnt;
signed main()
{

    fin>>a>>b;
    for(i=1;i<a.size();i++)
    {while(a[l]!=a[i] && l!=0)
        l=c[l-1];
     if(a[l]==a[i])
        l++;
     c[i]=l;
    }
    l=0;
    for(i=0;i<b.size();i++)
    {while(a[l]!=b[i] && l!=0)
        l=c[l-1];
        if(a[l]==b[i])
        l++;
        if(l==a.size())
        {cnt++;
         v[cnt]=i-a.size()+1;
         l=c[l-1];
        }

    }
    fout<<cnt<<'\n';
    if(cnt>1000)cnt=1000;
    for(i=1;i<=cnt;i++)
         fout<<v[i]<<" ";
    return 0;
}