Cod sursa(job #2180111)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 20 martie 2018 17:22:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
     
using namespace std;
     
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
 
vector < int > KMP(const string &A, const string &B) {
    string eval = A + "$" + B;
    int n = (int)eval.size();
    vector < int > pi(n);
 
    for(int i = 1, j = 0; i < n; ++i) {
        pi[i] = pi[i - 1];
        while(j > 0 && eval[i] != eval[j]) {
            j = pi[j - 1];
        }
        if(eval[i] == eval[j]) {
            ++j;
        }
        pi[i] = j;
    }

    vector < int > ret;
    for(int i = 0; i < n; ++i) {
        if(pi[i] == (int)A.size()) {
            ret.push_back(i - 2 * (int)A.size());
        }
    }
 
    return ret;
}
 
int main() {
    string A, B;
    fin >> A >> B;
 
    vector < int > ans = KMP(A, B);
 
    fout << (int)ans.size() << "\n";
    for(int i = 0; i < min((int)ans.size(), 1000); ++i) fout << ans[i] << " ";
    return 0;
}