Nu aveti permisiuni pentru a descarca fisierul grader_test10.ok

Cod sursa(job #552368)

Utilizator TeodoraTanaseTeodora Tanase TeodoraTanase Data 12 martie 2011 10:21:04
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

char p[2000005], t[2000005];
int n, m, b[2000005], a[2000005];

void citire()
{
    fgets(p,2000005);
    fgets(t,2000005);
    m=strlen(p);
    n=strlen(t);
}

void kmpPreprocess()
{
    int i=0, j=-1;
    b[i]=j;
    while (i<m)
    {
        while (j>=0 && p[i]!=p[j])
            j=b[j];
        i++;
        j++;
        b[i]=j;
    }
}

void kmpSearch()
{
    int i=0, j=0;
    while (i<n)
    {
        while (j>=0 && t[i]!=p[j])
            j=b[j];
        i++;
        j++;
        if (j==m)
        {
            a[++a[0]]=i-j;
            j=b[j];0
        }
    }
}

void afisare()
{
    printf ("%d\n",a[0]);
    for (int i=1; i<=min(1000,a[0]); i++)
        printf ("%d ",a[i]);
    printf ("\n");
}

int main()
{
    freopen ("strmatch.in","r",stdin);
    //freopen ("strmatch.out","w",stdout);
    citire();
    kmpPreprocess();
    kmpSearch();
    afisare();
    return 0;
}