Cod sursa(job #3159473)

Utilizator Maftei_TudorMaftei Tudor Maftei_Tudor Data 21 octombrie 2023 12:55:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <vector>
#include <cstring>

#define pb push_back

using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int N = 2e6 + 5;
typedef long long ll;

int k, lps[2*N];
char c1[N], c2[N], v[2*N];
vector<int> ans;

int main()
{
    in >> c1;
    in >> c2;

    int n = strlen(c1), m = strlen(c2);
    k = -1;
    for(int i=0; i<n; i++)
        v[++k] = c1[i];
    v[++k] = '#';
    for(int i=0; i<m; i++)
        v[++k] = c2[i];
    k++;

    for(int i=1; i<k; i++) {
        int j = lps[i-1];
        while(j > 0 && v[i] != v[j])
            j = lps[j-1];

        if(v[i] == v[j])
            j++;

        lps[i] = j;
        if(lps[i] == n) {
            ans.pb(i - n * 2);
        }
    }

    out << ans.size() << '\n';
    if(ans.size() <= 1000)
        for(int i=0; i<ans.size(); i++)
            out << ans[i] << ' ';
    else
        for(int i=0; i<1000; i++)
            out << ans[i] << ' ';
    return 0;
}