Cod sursa(job #3120553)

Utilizator Tudor_MateiHolota Tudor Matei Tudor_Matei Data 7 aprilie 2023 14:29:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
    #include <iostream>
    #include <fstream>
    #include <vector>

    using namespace std;
     ifstream fin("strmatch.in");
       ofstream fout("strmatch.out");
    void computeLPS(string A, int M, vector<int>& lps) {
        int len = 0;
        lps[0] = 0;
        int i = 1;
        while (i < M) {
            if (A[i] == A[len]) {
                len++;
                lps[i] = len;
                i++;
            }
            else {
                if (len != 0) {
                    len = lps[len - 1];
                }
                else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
    }

    void KMP(string A, string B) {
        int M = A.length();
        int N = B.length();
        vector<int> lps(M);
        computeLPS(A, M, lps);
        int i = 0, j = 0, count = 0;
        vector<int> positions;
        while (i < N) {
            if (A[j] == B[i]) {
                i++;
                j++;
            }
            if (j == M) {
                count++;
                positions.push_back(i - j);
                j = lps[j - 1];
            }
            else if (i < N && A[j] != B[i]) {
                if (j != 0) {
                    j = lps[j - 1];
                }
                else {
                    i++;
                }
            }
        }
        fout << count << endl;
        for (int k = 0; k < min(count, 1000); k++) {
            fout << positions[k] << " ";
        }
    }

    int main() {

        string A, B;
        fin >> A >> B;
        fin.close();

        KMP(A, B);
        fout.close();
        return 0;
    }