Cod sursa(job #1983337)

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

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

using namespace std;

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

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

    vector<int> lps(a.size(), 0);
    vector<int> result;
    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.pb(i - a.size());
        }
    }

    printf("%d\n", nr);
    for(int i=0; i < result.size(); i++)
        printf("%d ", result[i]);
}