Cod sursa(job #2266723)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 22 octombrie 2018 21:00:03
Problema Potrivirea sirurilor Scor 40
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()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s", s + 1);
    int n = strlen(s + 1), lrez = 0, m;
    m = n;
    s[n + 1] = 1;
    scanf("%s", s + n + 2);
    n = strlen(s + 1) - 1;
    int l = 0, r = 0;
    z[1] = 0;
    for(int i = 2; i <= n; i++) {
        /// z[i] = 0;
        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] + 1]) {
            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 - 2;
        }
    }
    printf("%d\n", lrez);
    for(int i = 1; i <= min(1000, lrez); i++)
        printf("%d ", rez[i]);
    return 0;
}