Cod sursa(job #2773012)

Utilizator BogdanRazvanBogdan Razvan BogdanRazvan Data 4 septembrie 2021 10:23:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

void usain_bolt()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
}

const int N = 2e6 + 5;

char s[N], t[N];
int pref[N], sol[N];

void prefix(int n)
{
    pref[1] = 0;
    int k = 0;
    for(int i = 2; i <= n; ++i) {
        while(s[i] != s[k + 1] && k > 0) k = pref[k];
        if(s[i] == s[k + 1]) ++k;
        pref[i] = k;
    }
}

int main()
{
    usain_bolt();

    fin >> (s + 1) >> (t + 1);
    int szs = strlen(s + 1);
    int szt = strlen(t + 1);
    prefix(szs);
    int k = 0;
    for(int i = 1; i <= szt; ++i) {
        while(t[i] != s[k + 1] && k > 0) k = pref[k];
        if(t[i] == s[k + 1]) ++k;
        if(k >= szs) {
            sol[++sol[0]] = i - szs;
        }
    }
    fout << sol[0] << "\n";
    for(int i = 1; i <= min(sol[0], 1000); ++i) {
        fout << sol[i] << " ";
    }
    return 0;
}