Cod sursa(job #2978957)

Utilizator 100pCiornei Stefan 100p Data 14 februarie 2023 18:01:53
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>

#define MAX 2000000
#define FILES freopen("strmatch.in","r",stdin);\
              freopen("strmatch.out","w",stdout);

using namespace std;

int lps[MAX + 5];
string a, b;
vector<int> ans;

int main()
{
    FILES
    cin >> a;
    int i = 0, j = 1;
    while(j < a.size())
    {
        while(i > 0 && a[j] != a[i])
            i = lps[i - 1];
        if(a[i] == a[j])
            lps[j] = lps[i] + 1;
        j++;
    }
    cin >> b;
    j = 0;
    for(int i = 0;i < b.size(); ++i)
    {
        while(j > 0 && b[i] != a[j])
            j = lps[j - 1];
        if(b[i] == a[j])
            j++;

        if(j == a.size()){
            ans.push_back(i - j);
            j = lps[j - 1];
        }
    }
    std::cout << ans.size() << '\n';
    for(int i = 0;i < min((int)(ans.size()), 1000); ++i)
        std::cout << ans[i] + 1 << ' ';
}