Cod sursa(job #1968050)

Utilizator trutruvasilicaHuhurez Marius trutruvasilica Data 17 aprilie 2017 14:04:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>

using namespace std;
char A[2000010],B[2000010];
int urm[2000010];
vector<int>pos;
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s\n%s",A+1,B+1);
    int n,m,i,k=0,nr=0;
    n=strlen(A+1);
    m=strlen(B+1);
    for(i=2;i<=n;i++)
    {
        while(k && A[k+1]!=A[i]) k=urm[k];
        if(A[k+1]==A[i]) k++;
        urm[i]=k;
    }
    k=0;
    for(i=1;i<=m;i++)
    {
        while(k && A[k+1]!=B[i]) k=urm[k];
        if(A[k+1]==B[i]) k++;
        if(k==n)
        {
            nr++;
            if(nr<=1000) pos.push_back(i-n);
        }
    }
    printf("%d\n",nr);
    for(unsigned i=0;i<pos.size();i++) printf("%d ",pos[i]);
}