Cod sursa(job #1897767)

Utilizator julianvladucuVladucu Iuliu Cristian julianvladucu Data 1 martie 2017 18:03:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <cstring>
#define nmax 2000005

using namespace std;
char a[nmax],b[nmax];
int p[1005],n,m,nr,poz[1005];

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",a+1);
    scanf("%s",b+1);
    int k=0;
    p[1]=0;
    n=strlen(a+1);
    m=strlen(b+1);
    for(int i=2;i<=n;i++)
        {
            while(k>0 && a[k+1]!=a[i])
                k=p[k];
            if(a[k+1]==a[i])
                k++;
            p[i]=k;
        }
    k=0;
    for(int i=1;i<=m;i++)
    {
        while(k>0 && a[k+1]!=b[i])
            k=p[k];
        if(a[k+1]==b[i])
            k++;
        if(k==n)
        {
            //k=p[m];
            nr++;
            if(nr<=1000)
                poz[nr]=i-n;
        }
    }
    printf("%d\n",nr);
    int min=nr<1000?nr:1000;
    if(nr)
    {
        for(int i=1;i<=min;i++)
            printf("%d ",poz[i]);
    }
    return 0;
}