Cod sursa(job #552376)

Utilizator Viva12Ferentz Sergiu Viva12 Data 12 martie 2011 10:36:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <string.h>
using namespace std;
char s[2000020];
char t[2000020];
int v[2000020];
int  b[2000020];
int n;
int m;
void citire()
{
    gets(s);
    gets(t);
    n=strlen(s);
    m=strlen(t);
}
void kmpp()
{
    int i=0;
    int j=-1;
    b[i]=j;
        while(i<n)
            {
                while(j>=0&&s[i]!=s[j])
                j=b[j];
                i++;
                j++;
               b[i]=j;
            }
}
int k;
int nr=0;
void kmps()
{
    int i=0;
    int j=0;
        while(i<m)
            {
             while(j>=0&&t[i]!=s[j])
             j=b[j];
             i++;
             j++;
             if(j==n)
                {
                    v[k++]=i-j;
                    nr++;
                    j=b[j];
                }

            }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
        citire();
        kmpp();
        kmps();
        printf("%d\n",nr);
        for(int i=0;i<k;i++)
            printf("%d ",v[i]);


    return 0;
}