Cod sursa(job #1528608)

Utilizator maria.nastaseNastase Maria maria.nastase Data 19 noiembrie 2015 21:06:00
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char s1[2000003],s2[2000003];
int x[2000001];
int s[1001];
int main()
{
    int k1,k2,c, kmp, sol=0;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s%s",s1,s2);
    k1=strlen(s1);
    k2=strlen(s2);
    if(k1>k2)
        printf("0");
    else
    {
        for(int i=k1; i>0; i--)
            s1[i]=s1[i-1];
        s1[k1+1]='\0';
        for(int i=k2; i>0; i--)
            s2[i]=s2[i-1];
        s2[k2+1]='\0';
        for(int i=2; i<=k1; i++)
        {
            c=i;
            while(s1[i]!=s1[x[c-1]+1] && c>1)
                c=x[c-1]+1;
            x[i]=c;
            if(c==1 && s1[1]!=s1[i])
                x[i]=0;
        }
        kmp=1;
        for(int i=1; i<=k2; i++)
        {
            while(s2[i]!=s1[kmp+1] && kmp>1)
                kmp=x[kmp-1]+1;
            x[i]=kmp;
            if(kmp==1 && s2[i]!=s1[1])
                x[i]=0;
        }
        for(int i=1; i<=k2 && sol<1000; i++)
        {
            if(x[i]==k1)
            {
                s[sol]=i-1;
                sol++;
            }
        }
        printf("%d\n",sol);
        for(int i=0;i<sol; i++)
            printf("%d ",s[i]);
    }
    return 0;
}