Cod sursa(job #2210342)

Utilizator giotoPopescu Ioan gioto Data 6 iunie 2018 12:08:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
using namespace std;

char p[2000005], t[2000005];
int pi[2000005], sol[2000005];
inline void make_prefix(int m){
    int k = 0;
    pi[1] = 0;
    for(int q = 2; q <= m ; ++q){
        while(k > 0 && p[k + 1] != p[q])
            k = pi[k];
        if(p[k + 1] == p[q]) ++k;
        pi[q] = k;
    }
}
int main(){
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s", p + 1);
    scanf("%s", t + 1);
    int m = strlen(p + 1);
    int n = strlen(t + 1);
    make_prefix(m);
    int q = 0, nr = 0;
    for(int i = 1; i <= n ; ++i){
        while(q > 0 && t[i] != p[q + 1])
            q = pi[q];
        if(t[i] == p[q + 1]) ++q;
        if(q == m){
            q = pi[m];
            ++nr;
            if(nr <= 1000)
                sol[nr] = i - m;
        }
    }
    printf("%d\n", nr);
    for(int i = 1; i <= min(nr, 1000) ; ++i)
        printf("%d ", sol[i]);
    return 0;
}