Cod sursa(job #1497890)

Utilizator stefanzzzStefan Popa stefanzzz Data 7 octombrie 2015 19:10:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAXN 2000010
using namespace std;

int kmp[MAXN], na, nb, solcnt;
char a[MAXN], b[MAXN];
vector<int> sol;

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

    scanf("%s\n%s", a + 1, b + 1);
    na = strlen(a + 1), nb = strlen(b + 1);
    for(int i = 2; i <= na; i++) {
        int x = kmp[i - 1];
        while(x && a[x + 1] != a[i])
            x = kmp[x];
        if(a[x + 1] == a[i]) ++x;
        kmp[i] = x;
    }

    int x = 0;
    for(int i = 1; i <= nb; i++) {
        while(x && a[x + 1] != b[i])
            x = kmp[x];
        if(a[x + 1] == b[i]) ++x;
        if(x == na) {
            ++solcnt;
            if(sol.size() < 1000) sol.push_back(i - na);;
            x = kmp[x];
        }
    }

    printf("%d\n", solcnt);
    for(auto x: sol)
        printf("%d ", x);
    printf("\n");

    return 0;
}