Cod sursa(job #3263569)

Utilizator sergioneUngureanu Sergiu sergione Data 15 decembrie 2024 04:28:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const string filename = "strmatch";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

int a_len, s_len, pi[4000005], afis;
vector <int> ans;
string a, b, s;

int main()
{
    fin >> a >> b;
    s = '$' + a + '$' + b;
    a_len = a.size();
    s_len = s.size();
    for(int i = 2; i < s_len; i++)
    {
        int k = pi[i - 1];
        while(k && s[i] != s[k + 1])
            k = pi[k];
        if(s[i] == s[k + 1])
            k++;
        pi[i] = k;
        if(k == a_len)
        {
            afis++;
            if(afis <= 1000)
                ans.push_back(i - 2 * a_len - 1);
        }
    }
    fout << afis << '\n';
    for(int x : ans)
        fout << x << ' ';
    return 0;
}