Pagini recente » Cod sursa (job #628299) | Cod sursa (job #2859578) | Cod sursa (job #78797) | Cod sursa (job #3234450) | Cod sursa (job #2466286)
#include <fstream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int nmax = 2e6 + 5;
char a[nmax], b[nmax];
class Kmp{
private:
int N, M;
int pi[nmax];
// prefix[i] = cel mai lung prefix pt s1 care este sufix pt s1(i) = primele i caractere
vector<int> kmp;
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++;
if(kmp.size() < 1000)
kmp.push_back(i - N);
k = pi[k];
}
}
g << nr <<"\n";
for(auto it : kmp)
g << it<<" ";
}
};
int main(){
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);
}