Cod sursa(job #1498521)

Utilizator MayuriMayuri Mayuri Data 8 octombrie 2015 18:32:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int NMAX = 2000004;
char P[NMAX], T[NMAX];
int pi[NMAX], n, m;
vector <int> sol;

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

    gets(P + 1);
    gets(T + 1);
    P[0] = T[0] = '#';
    n = strlen(P) - 1;
    m = strlen(T) - 1;
    P[0] = T[0] = 0;
    int rasp = 0;

    int k = 0;
    for(int i = 2; i <= n; ++ i) {
        while(k > 0 && P[k + 1] != P[i])
            k = pi[k];
        if(P[k + 1] == P[i])
            ++ k;
        pi[i] = k;
    }

    k = 0;
    for(int i = 1; i <= m; ++ i) {
        while(k > 0 && P[k + 1] != T[i])
            k = pi[k];
        if(P[k + 1] == T[i])
            ++ k;
        if(k == n) {
                k = pi[n];
            ++ rasp;
            if(rasp <= 1000)
                sol.push_back(i - n + 1);
        }
    }

    printf("%d\n", rasp);
    for(int i = 0; i < sol.size(); ++ i)
        printf("%d ", sol[i] - 1);

    return 0;
}