Cod sursa(job #2238926)

Utilizator al3xionescuIonescu Alexandru al3xionescu Data 8 septembrie 2018 13:44:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
#define NMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s, t;
vector <int> sol;
int q, n, m, i, pr[NMAX], cnt;
int main(){
    f >> s >> t;
    n = s.size();
    m = t.size();
    s = '#' + s;
    t = '#'+ t;
    for(i = 2; i <= n; i++){
        while(q && s[i] != s[q+1]){
            q = pr[q];
        }
        if(s[i] == s[q+1]){
            q++;
        }
        pr[i] = q;
    }
    q = 0;
    for(i = 1; i <= m; i++){
        while(q && t[i] != s[q + 1]){
            q = pr[q];
        }
        if(t[i] == s[q + 1]){
            q++;
        }
        if(q == n){
            q = pr[q];
            if(cnt < 1000){
                sol.push_back(i - n);
            }
            cnt++;
        }
    }
    g<< cnt << '\n';
    for(auto it : sol){
        g << it << ' ';
    }
    return 0;
}