Cod sursa(job #555912)

Utilizator sodamngoodSo Damn Good sodamngood Data 15 martie 2011 20:45:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 2000010

int N, M, sol;
int pi[maxn], potr[1024];
char P[maxn], T[maxn];

int main() {
    FILE *f1=fopen("strmatch.in", "r"), *f2=fopen("strmatch.out", "w");
    int i, k;

    fscanf(f1, "%s\n", P + 1);
    N = strlen(P + 1);
    fscanf(f1, "%s\n", T + 1);
    M = strlen(T + 1);

    k = 0;
    for(i=2; i<=N; i++) {
         while(k > 0 && P[i] != P[k + 1]) {
              k = pi[k];
         }

         if(P[i] == P[k + 1]) k ++;

         pi[i] = k;
    }

    k = 0;
    for(i=1; i<=M; i++) {
         while(k > 0 && T[i] != P[k + 1]) {
              k = pi[k];
         }

         if(T[i] == P[k + 1]) k ++;

         if(k == N) {
              sol ++;
              if(sol <= 1000) { potr[sol] = i - N; }
         }
    }

    fprintf(f2, "%d\n", sol);
    for(i=1; i<=min(sol, 1000); i++) {
         fprintf(f2, "%d ", potr[i]);
    } fprintf(f2, "\n");

    fclose(f1); fclose(f2);
    return 0;
}