Cod sursa(job #786214)

Utilizator kitzTimofte Bogdan kitz Data 10 septembrie 2012 18:18:18
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
// KMP_wikipedia.cpp : 
//#include "stdafx.h"
#include <fstream>
#define NMAX 2000005
using namespace std;
ifstream f ("strmatch.in"); ofstream g ("strmatch.out");
char P[NMAX], T[NMAX];
int k=-1, n, m, L[NMAX], s[1000], sk;
long long nr;
void kmp() 
{for (int t = 0; t < n; t++) {
       while (k > 0 && P[k+1] != T[t]) k = L[k];
       if (P[k+1] == T[t]) k++;
       if (k == m-1) {
         nr++; 
		 if(sk<1000) s[++sk] = t-m+1; 
         k = L[k]; 
	   } 
  }
}
int main()
{f>>P>>T;
 n = strlen(T);
 m = strlen(P);
 kmp();
 g<<nr<<"\n";
 for(int i=1;i<=sk;i++) g<<s[i]<<" ";
 g<<"\n";
 return 0;
}