Pagini recente » Cod sursa (job #3135977) | Cod sursa (job #432322) | Cod sursa (job #260935) | Cod sursa (job #2659603) | Cod sursa (job #2465230)
#include <fstream>
#include <string>
#include <cstring>
#include <vector>
#define nmax 500001
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
class Kmp{
private:
int N, M;
int pi[nmax + 5]; // prefix[i] = cel mai lung prefix pt s1 care este sufix pt s1(i) = primele i caractere
int kmp[nmax + 5];
public:
Kmp(int n, int m){
N = n;
M = m;
}
void prefix( char s1[] ){
int k = 0;
pi[1] = 0;
for ( int i = 2 ; i <= N; i++ ){
while( k > 0 && s1[k + 1] != s1[i] )
k = pi[k];
if( s1[k + 1] == s1[i])
k++;
pi[i] = k;
}
}
void kmp1(char s2[], char s1[]){
int k = 0, nr = 0;
for( int i = 1; i <=M; i++ ){
while( k > 0 && s1[k + 1] != s2[i] )
k = pi[k];
if( s1[k + 1] == s2[i] )
k++;
if( k == N ){
nr++;
kmp[nr] = i - N;
k = pi[k];
}
}
g << nr <<"\n";
for ( int i = 1; i <= nr ; i++)
g << kmp[i] <<" ";
}
};
int main(){
char a[nmax + 5], b[ nmax + 5];
int n, m, i;
f >> (a + 1)>> (b + 1);
n = strlen(a + 1);
m = strlen(b + 1);
Kmp text(n , m);
text.prefix(a);
text.kmp1(b, a);
}