Cod sursa(job #829012)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 4 decembrie 2012 19:38:38
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cstdio>
using namespace std;
#define N_MAX 2000010
int SOL;
char S[N_MAX], S2[N_MAX];
vector<int> strmatch(char *s, char *p) { //s string to be matched
    vector<int> solution;
    int n = strlen(s), m = strlen(p);
    int pi[n];
    memset(pi, 0, sizeof(pi));
    int k = 0;
    pi[0] = 0;
    for(int i = 1; i < n; i++) {
        while(k > 0 && s[k] != s[i]) {
            k = pi[k-1];
        }
        if(s[k] == s[i]) {
            k++;
        }
        pi[i] = k;
    }
    k = 0;
    for(int i = 0; i < m; i++) {
        while(k > 0 && s[k] != p[i]) {
            k = pi[k-1];
        }
        if(s[k] == p[i]) {
            k++;
        }
        if(k == n) {
            SOL++;
            if( solution.size() < 1000)
                solution.push_back(i-k+1);
            k = pi[k-1];
        }
    }
    return solution;
}


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

    cin >> S >> S2;
    vector <int> sol = strmatch(S, S2);
    printf("%d\n", SOL);
    for(int i = 0; i < sol.size(); i++) {
        printf("%d ", sol[i]);
    }

    return 0;
}