Cod sursa(job #2356562)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 26 februarie 2019 19:43:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int n,m,i,l,r,zalg[4000010];
vector<int> ans;
string S1,S2;

int main()
{
    f>>S1>>S2;n=S1.size();
    S1+='$';S1+=S2;l=r=1;m=S1.size();
    for(i=2;i<=m;i++)
        if(r<i)
        {
            r=i;
            while(S1[r-1]==S1[r-i]&&r<m)
                r++;
            r--;l=i;
            zalg[i]=r-i+1;
        }
        else
        {
            zalg[i]=min(zalg[i-l+1],r-i+1);
            if(zalg[i]==r-i+1)
            {
                while(S1[r]==S1[r-i+1]&&r<m)
                    r++;
                zalg[i]=r-i+1;
                l=i;
            }
        }
//    cout<<S1<<'\n';
//    for(i=1;i<=m;i++)
//        cout<<zalg[i]<<' ';
    for(i=1;i<=m;i++)
        if(zalg[i]==n)
            ans.push_back(i-n-2);
    g<<ans.size()<<'\n';
    for(i=0;i<ans.size()&&i<1000;i++)
        g<<ans[i]<<' ';
    return 0;
}