Cod sursa(job #2803490)

Utilizator cyg_alexandru546Zob Alexandru Mihai cyg_alexandru546 Data 20 noiembrie 2021 08:54:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");


/**
 * KMP[i] = lungimea celui mai lung prefix care este si sufix in s[0...i]
 *
 * KMP[i] = a   =>   s[0...(a-1)] = s[(i-a+1)...i]
 */
vector <int> KMP(string s)
{
    // Adaugam la misto un caracter, ca sa fie indexat de la 1
    s = "$" + s;

    vector <int> pi(s.size());

    // K = pi[i - 1]
    int k = 0;

    for (int i = 2; i < (int)s.size(); i++) {
        // Cat timp nu avem match
        while (k != 0 && s[i] != s[k + 1])
            k = pi[k];

        // Am gasit un match
        if (s[i] == s[k + 1])
            k++;

        // Daca NU am gasit match, conform while-ului, stim ca K=0

        pi[i] = k;
    }

    // Re-indexam de la 0
    pi.erase(pi.begin());

    return pi;
}

/**
 * Gaseste inceputul matchurilor lui s in t.
 */
vector <int> FindMatches(string s, string t)
{
    string to_kmp = s + "$" + t;
    vector <int> kmp = KMP(to_kmp);

    vector <int> ans;
    for (int i = (int)s.size() + 1; i < (int)kmp.size(); i++)
        if (kmp[i] == (int)s.size())
            ans.push_back(i - 2 * (int)s.size());

    return ans;
}


int main()
{
    string s,t;
    fin >> s;
    fin >> t;

    vector <int> ans = FindMatches(s,t);

    fout << ans.size() << '\n';

    for(auto i : ans)
        fout << i << ' ';

    fout << '\n';
}