Pagini recente » Cod sursa (job #3275930) | Cod sursa (job #2590766) | Cod sursa (job #2044711) | Cod sursa (job #1231368) | Cod sursa (job #719239)
Cod sursa(job #719239)
// Martie 2012 Dumitran Marius
// KMP O(n+m)
// Infoarena Arhiva Educationala Potrivirea Sirurilor
// Infoarena - Arhiva Educationala Potrivirea Sirurilor
// Februrie 2012 Marius Dumitran
// Rabin Karp O(n+m)
#include<string>
#include<iostream>
using namespace std;
#define maxn (1<<21)
string sir1, sir2;
int sol[ 2000 ], nr = 0;
int rez[maxn];
void prekmp( string sir, int * rez) {
int n = sir.size(), i = 0, j = -1;
rez[0] = -1;
while( i < n ) {
while( j >= 0 && sir[i] != sir[j]) // daca elementele nu sunt compatibile si nu am ajuns inca la inceput
j = rez[j]; // j ia urmataorea valoare posibila
i++; j++;
rez[i] = j;
}
}
int kmp( string sir1, string sir2, int *rez) {
int i = 0, j = 0;
int n = sir1.size(), m = sir2.size();
while (i < n ) {
while(j >= 0 && sir1[i] != sir2[j])
j = rez[j];
i++; j++;
if( j == m) {
sol[nr++] = i - j;
j = rez[j];
}
}
return nr;
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin>>sir1>>sir2;
int n = sir1.size(), m = sir2.size();
if( n > m ) {
printf("0\n");
return 0;
}
prekmp(sir1, rez);
printf("%d\n", kmp(sir2,sir1, rez));
for( int i = 0; i < nr && i < 1000; ++i)
printf("%d ", sol[i]);
printf("\n");
return 0;
}