Cod sursa(job #2141540)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 24 februarie 2018 13:33:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

vector<int> kmp(string &A, string &B) {
    int N = A.size(), M = B.size();
    vector<int> pi(N, -1), sol;
    int k = -1, i = 0;

    for (i = 1; i < N; i++) {
        while (k != -1 && A[i] != A[k + 1]) {
            k = pi[k];
        }

        if (A[i] == A[k + 1]) {
            k++;
        }
        pi[i] = k;
    }

    k = -1;
    for (i = 0; i < M; i++) {
        while (k != -1 && B[i] != A[k + 1]) {
            k = pi[k];
        }

        if (B[i] == A[k + 1]) {
            k++;
        }

        if (k == N - 1) {
            sol.push_back(i - N + 1);
        }
    }

    return sol;
}

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    string A, B;
    cin >> A >> B;
    
    vector<int> sol = kmp(A, B);
    
    cout << sol.size() << endl;
    for (int i = 0; i < sol.size() && i < 1000; i++) {
        cout << sol[i] << ' ';
    }
    return 0;
}