Cod sursa(job #1428189)

Utilizator stefanzzzStefan Popa stefanzzz Data 3 mai 2015 21:02:24
Problema Potrivirea sirurilor Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAXS 4000005
#define MIN(a, b) (((a) < (b))?(a):(b))
using namespace std;

int n, z[MAXS], l, r;
char s[MAXS];
vector<int> sol;

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

    int i;

    scanf("%s\n", s + 1);
    n = strlen(s + 1);
    scanf("%s", s + n + 1);
    
    l = 1; r = 0;
    for(i = 2; s[i] != '\0'; i++) {
        if(i > r) {
            l = i; r = i - 1;
            while(s[r + 1] == s[r - l + 2]) ++r;

            z[i] = r - l + 1;
        }
        else {
            int x = i - l + 1;
            
            if(z[x] < r - i + 1)
                z[i] = z[x];
            else {
                l = i;
                while(s[r + 1] == s[r - l + 2]) r++;
                z[i] = r - l + 1;
            }
        }

        if(z[i] >= n)
            sol.push_back(i - n - 1);
    }

    printf("%d\n", sol.size());
    for(i = 0; i < sol.size() && i < 1000; i++)
        printf("%d ", sol[i]);
    printf("\n");

    return 0;
}