Cod sursa(job #1497793)

Utilizator stefanzzzStefan Popa stefanzzz Data 7 octombrie 2015 12:48:40
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAXN 4000500
#define MIN(a, b) (((a) < (b))?(a):(b))
using namespace std;

int na, n, z[MAXN], solcnt;
char s[MAXN];
vector<int> sol;

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    scanf("%s", s);
    na = strlen(s);
    s[na] = '$';
    scanf("%s", s + na + 1);
    n = strlen(s);

    int l = 0, r = 0;
    for(int i = 1; i < n; i++) {
        if(r < i) {
            int j, k;
            for(j = i, k = 0; j < n && s[j] == s[k]; j++, k++);
            z[i] = j - i;
            if(i + z[i] - 1 > r) r = z[i], l = i;
        }
        else {
            int x = i - l;
            z[i] = MIN(z[x], r - i + 1);
            int j, k;
            for(j = i + z[i], k = z[i]; j < n && s[j] == s[k]; j++, k++);
            z[i] = j - i;
            if(i + z[i] - 1 > r) r = z[i], l = i;
        }
        if(i > na && z[i] == na) {
            ++solcnt;
            if(sol.size() < 1000) sol.push_back(i - na - 1);
        }
    }

    printf("%d\n", solcnt);
    for(auto x: sol)
        printf("%d ", x);
    printf("\n");

    return 0;
}