Cod sursa(job #2290771)

Utilizator gabiluciuLuciu Gabriel gabiluciu Data 26 noiembrie 2018 22:47:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#define nl '\n'
using namespace std;

int main() {

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

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    string N,M;
    cin >> M >> N;
    int n = N.size(),m = M.size();
    int lps[m];
    lps[0] = 0;
    int i=1;
    int len = 0;
    while (i<m){
        if(M[i] == M[len] ){
            ++len;
            lps[i] = len;
            ++i;
        }else{
            if(len){
                len = lps[len-1];
            }else
                lps[i] = 0,++i;
        }
    }
    i=0;
    len = 0;
    int cnt = 0;
    vector<int> sol;
    while (i<n){
        if(N[i] == M[len]){
            ++i;
            ++len;
        }
        if(len == m){
            ++cnt;
            if(cnt<=1000)
                sol.push_back(i-m);
            len = lps[len-1];
        }
        else if(M[len]!=N[i] && i<n){
            if(len)
                len = lps[len-1];
            else ++i;
        }

    }
    cout << cnt << nl;
    for_each(sol.begin(),sol.end(),[](int a){cout << a << ' ';});
}