Cod sursa(job #2066716)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 15 noiembrie 2017 12:54:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

char pat[2000005], txt[2000005];
int dp[2000005], n, m;
int nsol, sol[1005];

void buildPre() {
    int len = 0, i = 1;
    dp[0] = 0;

    while(i < n) {
        if(pat[len] == pat[i]) {
            ++ len;
            dp[i] = len;
            ++ i;
        } else {
            if(len > 0) {
                len = dp[len - 1];
            } else {
                dp[i] = 0;
                ++ i;
            }
        }
    }
}

void searchKmp() {
    int i = 0, j = 0;

    while(j < m) {
        if(pat[i] == txt[j]) {
            ++ i;
            ++ j;
        }

        if(i == n) {
            ++ nsol;
            if(nsol <= 1000) {
                sol[nsol] = j - i;
            }
            i = dp[i - 1];
        } else if(j < m && pat[i] != txt[j]){
            if(i > 0) {
                i = dp[i - 1];
            } else {
                ++ j;
            }
        }
    }
}

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

    gets(pat);
    gets(txt);

    n = strlen(pat);
    m = strlen(txt);

    buildPre();
    searchKmp();

    printf("%d\n", nsol);
    for(int i = 1; i <= min(1000, nsol); ++ i) {
        printf("%d ", sol[i]);
    }

    return 0;
}