Cod sursa(job #1500740)

Utilizator SzymonSidorSzymonSidor SzymonSidor Data 12 octombrie 2015 17:35:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <algorithm>
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

vector <int> KmpPrefix(string strS) {
    vector <int> prefix(strS.size(), 0);

    for (int i = 2, k = 0; i < strS.size(); i++) {
        for (; k && strS[i] != strS[k + 1]; k = prefix[k]);
        if (strS[i] == strS[k + 1])
            k++;
        prefix[i] = k;
    }

    return prefix;
}

vector <int> KMP(string strMare, string strMic, vector <int> prefix) {
    vector <int> solutions;

    for (int i = 1, k = 0; i < strMare.size(); i++) {
        for (; k && strMare[i] != strMic[k + 1]; k = prefix[k]);
        if (strMare[i] == strMic[k + 1])
            k++;
        if (k == strMic.size() - 1) {
            solutions.push_back(i - k);
            k = prefix[k];
        }
    }
    
    return solutions;
}

int main() {
    ifstream cin("strmatch.in");
    freopen("strmatch.out", "w", stdout);

    string strS, strB;
    cin >> strS;
    cin >> strB;

    strS = " " + strS;
    strB = " " + strB;

    vector <int> sol = KMP(strB, strS, KmpPrefix(strS));

    printf("%d\n", sol.size());
    for (int i = 0; i < min(1000, (int) sol.size()); i++)
        printf("%d ", sol[i]);

    return 0;
}