Cod sursa(job #2407921)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 17 aprilie 2019 12:44:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include<bits/stdc++.h>
using namespace std;

const int maxN=(2e6)+1;

char a[2*maxN],p[maxN],s[maxN];
int z[2*maxN],st,dr,sz;
vector<int> sol;
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    scanf("%s",p+1);
    scanf("\n");
    scanf("%s",s+1);

    strcpy(a+1,p+1);
    strcat(a+1,s+1);

    int n=strlen(p+1);
    int m=strlen(s+1);

    for(int i=2;i<=n+m;i++)
    {
        if(dr>=i) z[i]=min(z[i-st+1],dr-i+1);
        while((i+z[i])<=(n+m) && a[1+z[i]]==a[i+z[i]]) z[i]++;
        if(i+z[i]-1>dr)
        {
            dr=i+z[i]-1;
            st=i;
        }
    }

    for(int i=n+1;i<=n+m;i++)
        if(z[i]>=n)
        {
            sz++;
            if(sz<=1000) sol.push_back(i-n-1);
        }

    printf("%d\n",sz);
    for(auto it:sol)
        printf("%d ",it);

    printf("\n");
    return 0;
}