Cod sursa(job #3238217)

Utilizator adelinapetreAdelina Petre adelinapetre Data 23 iulie 2024 14:29:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");

vector <int> sol;

vector <int> prefix(string s)
{
    int n = (int)s.length();
    vector <int> kmp(n);
    for (int i = 1; i < n; i++)
    {
        int j = kmp[i-1];
        while (j > 0 && s[i] != s[j])
            j = kmp[j - 1];
        if (s[i] == s[j])
            j ++;
        kmp[i] = j;
    }
    return kmp;
}

vector <int> matching(string s, string t)
{
    string c = s + '!' + t;
    vector <int> lg = prefix(c);
    vector <int> poz;
    for (int i = s.size() + 1; i < c.size(); i ++)
    {
        if (lg[i] >= s.size())
            poz.push_back(i - s.size());
    }
    return poz;
}

int main()
{
    string a, b;
    cin >> a >> b;
    sol = matching(a, b);
    cout << sol.size() << '\n';
    for (int i = 0; i < min((int)sol.size(), 1000); i ++)
        cout << sol[i] - a.size() << " ";
    return 0;
}