Cod sursa(job #2017113)

Utilizator LucaSeriSeritan Luca LucaSeri Data 31 august 2017 12:24:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;

const int maxlen = 4e6 + 20;

char s[maxlen];
int z[maxlen];

int cnt = 0;

int ans[1010];

void Zalg(int len, int n){
    z[1] = 0;
    int l = 1, r = 1;
    for(int i = 2; i <= n; ++i){
        if(i > r){
            while(z[i]+i <= n && s[z[i]+i] == s[z[i]+1]) ++z[i];
            l = i;
            r = i + z[i] - 1;
        }
        else {
            z[i] = min(r-i, z[i-l+1]);
            while(z[i]+i <= n && s[z[i]+i] == s[z[i]+1]) ++ z[i];
            if(z[i] + i - 1 > r){
                l = i;
                r = i + z[i]-1;
            }
        }
        if(z[i] == len){
            if(cnt < 1000){
                ans[cnt] = i - len - 2;
            }
            ++cnt;
        }
    }
}
ifstream f("strmatch.in");
ofstream g("strmatch.out");

int main()
{
    f >> (s+1);
    int len = strlen(s+1);
    s[len+1] = '#';
    f >> (s+len+2);
    int n = strlen(s + 1);
    Zalg(len, n);

    g << cnt << '\n';
    for(int i = 0; i < cnt && i < 1000; ++i){
        g << ans[i] << ' ';
    }
    return 0;
}