Cod sursa(job #3182867)

Utilizator Radu_MocanasuMocanasu Radu Radu_Mocanasu Data 9 decembrie 2023 22:48:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>
#define NMAX 2000000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int z[NMAX * 2 + 5];
char s[NMAX * 2 + 5];
char t[NMAX + 5];
vector <int> v;
int main()
{
    int n,i,j,l = 0,r = 0,cnt = 0,sz;
    fin >> s;
    n = strlen(s);
    fin.get();
    fin >> t;
    sz = n + strlen(t);
    strcat(s,t);
    for(i = 1; i < sz; i++){
        if(i < r) z[i] = min(r - i, z[i - l]);
        while(i + z[i] < sz && s[z[i]] == s[i + z[i]]) z[i]++;
        if(i + z[i] > r){
            l = i;
            r = i + z[i];
        }
        if(z[i] >= n && i >= n){
            cnt++;
            if(v.size() < 1000) v.push_back(i - n);
        }
    }
    fout << cnt << "\n";
    for(auto x : v) fout << x << " ";
    return 0;
}