Cod sursa(job #713776)

Utilizator Sm3USmeu Rares Sm3U Data 14 martie 2012 22:19:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <cstdio>
#include <cstring>
#define nMax 2000100

using namespace std;

char a[nMax];
char b[nMax];
int kmp[nMax];
int n;
int m;
int StrStr[1010];
int nStrStr;

void prefix()
{
    int q = 0;
    for (int i = 2; i < n; ++ i){
        while (q && a[q + 1] != a[i]){
            q = kmp[q];
        }
        if (a[q + 1] == a[i]){
            q ++;
        }
        kmp[i] = q;
    }
}

void citire()
{
    gets (a + 1);
    gets (b + 1);
    n = strlen (a + 1) + 1;
    m = strlen (b + 1) + 1;
    prefix();
}

void StrStrEficient()
{
    int q = 0;
    for (int i = 1; i < m; ++ i){
        while (q && a[q + 1] != b[i]){
            q = kmp[q];
        }
        if (a[q + 1] == b[i]){
            q++;
        }
        if (q == n - 1){
            q = kmp[q];
            nStrStr ++;
            if (nStrStr <= 1000){
                StrStr[nStrStr] = i - n + 1;
            }
        }
    }
}

void afis()
{
    printf ("%d\n", nStrStr);
    int N = (nStrStr <= 1000) ? nStrStr : 1000;
    for (int i = 1; i <= N; ++ i){
        printf ("%d ", StrStr [i]);
    }
    printf ("\n");
}

int main()
{
    freopen ("strmatch.in", "r", stdin);
    freopen ("strmatch.out", "w", stdout);
    citire();
    StrStrEficient();
    afis();

    return 0;
}