Cod sursa(job #2705062)

Utilizator vladm98Munteanu Vlad vladm98 Data 11 februarie 2021 20:30:14
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;
int kmp[4000011];

int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    string target, source, s;
    fin >> target >> source;
    s = "$" + target + "$" + source;
    kmp[1] = 0;

    for (int i = 2;  i < s.size(); ++i) {
        int answer = kmp[i - 1];
        while(answer != 0 && s[answer + 1] != s[i]) {
            answer = kmp[answer];
        }
        if (s[answer + 1] == s[i]) {
            answer += 1;
        }
        kmp[i] = answer;
    }
    int cnt = 0;
    for (int i = target.size() + 2; i < s.size(); ++i) {
        if (kmp[i] == target.size()) {
            cnt += 1;
        }
    }
    cnt = 0;
    fout << cnt << "\n";
    for (int i = target.size() + 2; i < s.size(); ++i) {
        if (kmp[i] == target.size()) {
            cnt += 1;
            if (cnt == 1001) {
                break;
            }
            int result = i - 2 * target.size() - 1;
            fout << result << " ";
        }
    }

    return 0;
}