Cod sursa(job #805978)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 1 noiembrie 2012 16:05:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
char A[2000010],B[2000010];
int pi[2000010],LA,LB,N;
vector<int> PO;
void prefix()
{
    int q=0;
    pi[1]=0;
    for(int i=2;i<=LA;i++)
    {
        while(q>0&&A[q+1]!=A[i]) q=pi[q];
        if(A[q+1]==A[i]) q++;
        pi[i]=q;
    }
}
void potrivire()
{
    int q=0;
    for(int i=1;i<=LB;i++)
    {
        while(q>0&&A[q+1]!=B[i]) q=pi[q];
        if(A[q+1]==B[i]) q++;
        if(q==LA)
        {
            N++;
            if(N<=1000) PO.push_back(i-q);
            q=pi[q];
        }
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",A+1);
    scanf("%s",B+1);
    LA=strlen(A+1);
    LB=strlen(B+1);
    prefix();
    potrivire();
    printf("%d\n",N);
    for(vector<int>::iterator it=PO.begin();it!=PO.end();it++)
        printf("%d ",*it);
    return 0;
}