Cod sursa(job #2675072)

Utilizator AntoniuFicAntoniu Ficard AntoniuFic Data 21 noiembrie 2020 09:50:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

void buildLPS(vector<int> &lps, string a){
    lps.reserve(a.length());
    for (int i = 0; i < a.length(); ++i) {
        lps.push_back(0);
    }
    for (int i = 1, j = 0; i < a.length(); ++i) {
        if(a[i] == a[j]) lps[i] = ++j;
        else if(j) j = lps[j - 1], --i;
        else lps[i] = 0;
    }
}

void kmp(vector<int> &matches, vector<int> lps, string a, string b){
    for (int i = 0, j = 0; i < b.length();) {
        if(a[j] == b[i]){
            ++i, ++j;
            if(j == a.length()) matches.push_back(i - j), j = lps[j - 1];
        }
        else if(i < b.length() && a[j] != b[i]){
            if(j) j = lps[j - 1];
            else ++i;
        }
        if(matches.size() >= 1000) return;
    }
}

int main() {
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    string a, b;
    f>>a>>b;
    vector<int> matches;
    vector<int> lps;
    buildLPS(lps, a);
    kmp(matches, lps, a, b);
    int l = matches.size();
    if(1000 < matches.size())
        l = 1000;
    g<<l<<'\n';
    for (int i = 0; i < l; ++i) {
        g<<matches[i]<<' ';
    }
    return 0;
}