Pagini recente » Cod sursa (job #223998) | Cod sursa (job #1631061) | Cod sursa (job #621999) | Cod sursa (job #2337326) | Cod sursa (job #978242)
Cod sursa(job #978242)
#include<fstream>
#include<iostream>
#include<string>
#define NMAX 2000001
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int sol[NMAX];
int pi[NMAX];
string A, B;
int dim = 0;
void read(){
f>>A;
f>>B;
}
void KMP_prefix(string A){
int k = 0, N, i;
N = A.size();
pi[k] = 0;
for(i = 1; i < N; i++){
while(k > 0 && A[k] != A[i])
k = pi[k];
if(A[k] == A[i])
k++;
pi[i] = k;
}
}
void KMP_match(string A, string B){
int t = 0, N = A.size(), M = B.size();
int i = 0;
while(i < M){
while(t > 0 && A[t] != B[i])
t = pi[i];
if(A[t] == B[i])
t++;
if(t == N){
sol[dim] = i - N + 1;
dim++;
i = i - N + 2;
}
else
i++;
}
}
void print(){
int i;
g<<dim<<"\n";
for(i = 0; i < dim; i++)
g<<sol[i]<<" ";
}
int main(){
read();
KMP_prefix(A);
KMP_match(A, B);
print();
return 0;
}