Cod sursa(job #2365275)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 4 martie 2019 12:45:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include<bits/stdc++.h>
#define maxN 2000005
using namespace std;
int urm[maxN],n,m,l,dv,v[maxN];
char p[maxN],t[maxN];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",p+1);
    scanf("%s",t+1);
    n=strlen(t+1);
    m=strlen(p+1);
    int k=0;
    urm[1]=0;
    for(int i=2;i<=m;i++)
    {
        while(k>0 && p[i]!=p[k+1]) k=urm[k];
        if(p[i]==p[k+1]) k++;
        urm[i]=k;
    }
     k=0;
    for(int i=1;i<=n;i++)
    {
        while(k>0 && p[k+1]!=t[i])
        {
            k=urm[k];
        }
        if(t[i]==p[k+1]) k++;
        if(k==m)
        {
            v[++dv]=i-m;
        }
    }
    printf("%d\n",dv);
    for(int i=1;i<=min(dv,1000);i++) printf("%d ",v[i]);
    printf("\n");
    return 0;
}