Cod sursa(job #2337821)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 6 februarie 2019 18:49:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,m,i,j,l,r,ans,k,zalg[4000010];
string A,B;

int main()
{
    f>>A>>B;
    m=A.size();
    A+='1';A+=B;
    n=A.size();
    for(i=2;i<=n;i++)
    {
        if(i>r)
        {
            for(j=i;j<=n;j++)
                if(A[j-1]!=A[j-i])
                    break;
            zalg[i]=j-i;
            l=i;r=j-1;
        }
        else
        {
            zalg[i]=min(r-i+1,zalg[i-l+1]);
            if(zalg[i]==r-i+1)
            {
                for(j=r+1;j<=n;j++)
                    if(A[j-1]!=A[j-i])
                        break;
                zalg[i]=j-i;
                l=i,r=i+zalg[i]-1;
            }
        }
        if(zalg[i]==m)
            ans++;
    }
//    g<<A<<'\n';
//    for(i=1;i<=n;i++)
//        g<<zalg[i]<<' ';g<<'\n';
    g<<ans<<'\n';
    int cnt=1000;
    for(i=1;i<=n&&cnt;i++)
        if(zalg[i]==m)
            cnt--,g<<i-m-2<<' ';
    return 0;
}