Cod sursa(job #952229)

Utilizator primulDarie Sergiu primul Data 22 mai 2013 21:46:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include<stdio.h>
#include<string.h>
  
using namespace std;
char p[2000005],t[2000005];
int F[2000005],i,j,m,n,pos[1005];
void constructie_pi()
{
    m=strlen(p);
    F[0]=F[1]=0;
    for(i=2;i<=m;i++)
    {
        j=F[i-1];
        for(;;)
        {
            if(p[i-1]==p[j])
                {
                    F[i]=j+1;break;
                }
            if(j==0)
            {
                F[i]=0; break;
            }
            else j=F[j];
        }
    }
  
}
void KMP()
{
    constructie_pi();
    n=strlen(t);
    i=0;
    j=0;
    for(;;)
    {
        if(j==n)
            break;
        if(t[j]==p[i])
        {
            i++;
            j++;
            if(i==m)
                {
  
                        pos[0]++;
                        if(pos[0]<=1000)
                            {
                                pos[pos[0]]=j-m;
                            }
                    }
  
  
  
        }
        else if(i>0) i=F[i];
        else j++;
  
    }
  
  
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",p);
    scanf("%s",t);
    KMP();
    printf("%d\n",pos[0]);
    if(pos[0]>1000)
        pos[0]=1000;
    for(i=1;i<=pos[0];i++)
        printf("%d ",pos[i]);
    printf("\n");
  
    return 0;
}