Cod sursa(job #1983340)

Utilizator lraduRadu Lucut lradu Data 21 mai 2017 18:28:29
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define mod 1000000007
#define PI 3.141592653589793;

using namespace std;

int lps[4000005];
int result[1002];

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

    string a, b;
    getline(cin, a);
    getline(cin, b);

    int ind = 0, i = 1, j = 0, n = a.size(), m = b.size(), nr = 0;
    while(i < n){
        if(a[i] == a[ind]){
            lps[i] = ind + 1;
            i++;
            ind++;
        } else if(ind){
            ind = lps[ind - 1];
        } else {
            i++;
        }
    }

    i = 0;
    while(i < m){
        if(b[i] == a[j]) {
            i++;
            j++;
        } else if(j){
            j = lps[j - 1];
        } else {
            i++;
        }

        if(j == a.size()){
            nr++;
            j = lps[j-1];
            if(nr <= 1000)
                result[nr] = i - n;
        }
    }

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