Cod sursa(job #1068194)

Utilizator Vladinho97Iordan Vlad Vladinho97 Data 27 decembrie 2013 23:51:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>
#include <cstring>
using namespace std;
char n[2000009],m[2000009];
int p[2000009],v[1001],N;
void prefixe()
{
    int k,i;
    p[1]=0;
    k=0;
    for(i=2;i<=N;i++)
    {
        if(k>0&&n[k+1]!=n[i])
            k=p[k];
        if(n[k+1]==n[i])
            k++;
        p[i]=k;
    }
}
int main()
{
    int i,lung,q,nr=0;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%c",&n[1]);
    i=1;
    while(n[i]!='\n')
    {
        i++;
        scanf("%c",&n[i]);
    }
    N=i-1;
    scanf("%c",&m[1]);
    i=1;
    while(m[i]!='\n')
    {
        i++;
        scanf("%c",&m[i]);
    }
    lung=i-1;
    prefixe();
    q=0;
    for(i=1;i<=lung;i++)
    {
        while(m[i]!=n[q+1]&&q>0)
        {
            q=p[q];
        }
        if(m[i]==n[q+1])
        {
            q++;
        }
        if(q==N)
        {
            nr++;
            if(nr<=1000)
                v[nr]=i-N;
        }
    }
    printf("%d\n",nr);
    for(i=1;i<=nr;i++)
        printf("%d ",v[i]);
    return 0;
}