Cod sursa(job #2266775)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 22 octombrie 2018 21:23:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

char s[4000020];
int z[4000020];
int rez[1010];

int main()
{
    ios_base::sync_with_stdio(false);
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin.getline(s, 4000020);
    int n = fin.gcount() - 1, lrez = 0, m;
    m = n;
    s[n] = '#';
    fin.getline(s + n + 1, 4000020);
    n += fin.gcount() - 1;
    int l = 0, r = 0;
    for(int i = 1; i < n; i++) {
        if(i <= r) {
            z[i] = min(z[i - l], r - i + 1);
        }
        while(i + z[i] - 1 < n && s[i + z[i]] == s[z[i]]) {
            z[i]++;
        }
        if(i + z[i] - 1 >= r) {
            r = i + z[i] - 1;
            l = i;
        }
        if(z[i] == m) {
            lrez++;
            if(lrez <= 1000)
                rez[lrez] = i - m - 1;
        }
    }
    fout << lrez << '\n';
    for(int i = 1; i <= min(1000, lrez); i++)
        fout << rez[i] << ' ';
    return 0;
}