Cod sursa(job #2739247)

Utilizator Cosmin2004_InfoMoldoveanu Cosmin Cosmin2004_Info Data 7 aprilie 2021 13:02:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void kmp(string& s, int* lps) {
    int k = 0, len = s.length();
    lps[1] = 0;
    for(int i = 2; i < len; i++) {
        while(k && s[k + 1] != s[i]) k = lps[k];
        if(s[k + 1] == s[i]) k++;
        lps[i] = k;
    }
}
const int NMAX = 2e6;
int lps[NMAX + 5];
string s, t;

int main()
{
    fin >> s >> t; s = " " + s; t = " " + t;
    kmp(s, lps);
    int res = 0;
    vector <int> sol;
    int len = t.length(), k = 0, n = s.length() - 1; s += " ";
    for(int i = 1; i < len; i++) {
        while(k && s[k + 1] != t[i]) k = lps[k];
        if(s[k + 1] == t[i]) k++;
        if(k == n) {
            res++;
            if(res <= 1000) sol.push_back(i - n);
        }
    }
    fout << res << "\n";
    for(auto el : sol) fout << el << " ";
    return 0;
}