Cod sursa(job #2290011)

Utilizator gabiluciuLuciu Gabriel gabiluciu Data 25 noiembrie 2018 17:29:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define nl '\n'
using namespace std;
int v[200002];
char s[200002];
char m[200002];
int main() {
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    cin >> s+1 >> m+1;
    int l1= strlen(s+1),l2=strlen(m+1);
    int k=1;
    for(auto i=2;i<=l1;++i){
        if(s[i]==s[k]){
            v[i] = k;
            ++k;
        }else{
            k = 1;
            v[i] = 0;
        }
    }
    k=0;
    auto cnt = 0;
    vector<int> sol;
    for(int i=1;i<=l2;){
        if(m[i]==s[k+1]){
            ++i;
            ++k;
            if(k==l1){
                ++cnt;
                sol.push_back(i-l1-1); // indexare de la 0
            }
        }else{
            if(!k) ++i;
            else k = v[k];
        }
    }
    cout << cnt << nl;
    for_each(sol.begin(),sol.end(),[](int n){cout << n << ' ';});
    return 0;
}