Cod sursa(job #2803493)

Utilizator cyg_alexandru546Zob Alexandru Mihai cyg_alexandru546 Data 20 noiembrie 2021 09:02:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

vector <int> KMP(string s)
{
    s = "$" + s;

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

    int k = 0;

    for(int i = 2; i < (int)s.size(); i++)
    {
        while(k != 0 && s[i] != s[k+1])
            k = pi[k];

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

    return pi;
}

int cnt = 0;

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*s.size()-1), cnt++;
    }
    return ans;
}

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

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

    fout << cnt <<'\n';

    for(int i = 0; i < min(cnt, 1000); i++)
    {
        fout << ans[i]<<" ";
    }
}