Pagini recente » Cod sursa (job #822213) | Cod sursa (job #764695) | Cod sursa (job #1949359) | Cod sursa (job #2357191) | Cod sursa (job #805725)
Cod sursa(job #805725)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int N=2000002;
int pref[N];
string A,B;
vector <int> results;
int result;
class KMP{
string A,B;
int appereances;
vector <int> appereances_positions;
const int STR_MAX;
int *fail;
public:
KMP(string X,string Y,int maxString=2000100):STR_MAX(maxString){
A=X;
B=Y;
fail=new int[STR_MAX];
appereances=0;
this->createFail();
this->patternMatch();
}
bool createFail(){
int failValue,i;
fail[0]=fail[1]=0;
for(i=2;i<=A.length();++i){
failValue=fail[i-1];
while(A[failValue]!=A[i-1] && failValue){
failValue=fail[failValue];
}
if(A[failValue]==A[i-1]){
fail[i]=failValue+1;
}
}
return true;
}
bool patternMatch(){
int i,currentstate=0;
for(i=0;i<B.length();++i){
if(B[i]==A[currentstate]){
currentstate++;
}
else{
while(A[currentstate]!=B[i] && currentstate){
currentstate=fail[currentstate];
}
if(B[i]==A[currentstate]){
currentstate++;
}
}
if(currentstate==A.length()){
currentstate=fail[currentstate];
appereances++;
appereances_positions.push_back(i-A.length()+1);
}
}
return true;
}
int getApparitions(){
return appereances;
}
vector<int> getAppPositions(){
return appereances_positions;
}
};
int main(){
vector <int> results;
vector <int>::iterator result;
in>>A>>B;
KMP algoritm(A,B);
out<<algoritm.getApparitions()<<"\n";
results=algoritm.getAppPositions();
for(result=results.begin();result!=results.end();result++){
out<<*result<<" ";
}
return 0;
}