Cod sursa(job #2930120)

Utilizator 100pCiornei Stefan 100p Data 27 octombrie 2022 15:45:00
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define MAX 2000000
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define FILES freopen("strmatch.in","r",stdin);\
              freopen("strmatch.out","w",stdout);
using namespace std;
string path, str;
int lps[MAX + 5];
vector<int> ans;
int main()
{
    fastio
    FILES
    cin >> path >> str;
    int i = 0;
    lps[0] = 0;
    for(int j = 1;j < path.size(); ++j)
    {
        while(i && path[i] != path[j])
            i = lps[i];
        if(path[i] == path[j])
            lps[j] = i + 1, i++;
        else lps[j] = 0;
    }
    int j = 0;
    for(int i = 0;i < str.size(); ++i)
    {
        while(j && str[i] != path[j])
            j = lps[j-1];
        if(path[j] == str[i])
            j++;
        if(j == path.size())
            j = lps[j], ans.push_back(i + 1);
    }
    cout << ans.size() << '\n';
    for(auto i : ans)
        cout << i - path.size() << ' ';
}