Cod sursa(job #1376548)

Utilizator GilgodRobert B Gilgod Data 5 martie 2015 17:48:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

#define MAXL 2000005

FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");

char A[MAXL+1], B[MAXL+1];
int PI[MAXL+1];
int n, m;
int pos[1001];

inline void constr_prefix(){
// table:
/*
*   char: |a|b|a
*   index:|0|1|2
*   value:|0|0|1
*   for "abab" -> prefixes = {"aba", "ab", a"}
*              -> suffixes = {"bab", "ab", b"}
*/

    PI[1] = 0;
    int k = 0;
    for(int i = 1; i < n; i++) {
        while((k>0) && (A[k] != A[i])) k = PI[k-1];
        if(A[k] == A[i]) k++;
        PI[i] = k;
    }
}

int main()
{
    int rd = fscanf(fin, "%s\n%s", A,B);
    n = strlen(A);
    m = strlen(B);

    constr_prefix();
    int matched = 0;
    int k = 0;
    for(int i = 0; i < m; i++) {
        while((k > 0) && (A[k] != B[i])) k = PI[k-1];
        if(A[k] == B[i]) k++;
        if(k==n) {
            matched++;
            if(matched<= 1000) pos[matched-1] = i-n+1;
        }
    }
    fprintf(fout, "%d\n", matched);
    int N = (matched > 1000)?1000:matched;
    for(int i = 0; i < N; i++)
        fprintf(fout, "%d ", pos[i]);
    fprintf(fout, "\n");
    fclose(fout);
}