Cod sursa(job #1983336)

Utilizator lraduRadu Lucut lradu Data 21 mai 2017 18:14:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 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;
    cin>>a>>b;

    vector<int> lps(a.size(), 0);
    vector<int> result;
    int ind = 0, i = 1, j = 0;
    while(i < a.size()){
        if(a[i] == a[ind]){
            lps[i] = ind + 1;
            i++;
            ind++;
        } else if(ind){
            ind = lps[ind - 1];
        } else {
            i++;
        }
    }

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

        if(j == a.size()){
            result.pb(i - a.size());
            j = lps[j-1];
            if(result.size() == 1000) break;
        }
    }

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