Cod sursa(job #2337808)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 6 februarie 2019 18:42:35
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 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[2000010];
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<<ans<<'\n';
    for(i=1;i<=n;i++)
        if(zalg[i]==m)
            g<<i-2*m+1<<' ';
    return 0;
}