Pagini recente » Cod sursa (job #1009799) | Cod sursa (job #1015216) | Cod sursa (job #1684035) | Cod sursa (job #2611081) | Cod sursa (job #679259)
Cod sursa(job #679259)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
int match(string s, string w, vector<int> t, vector<int>& res){
int m = 0;
int i = 0;
int counter = 0;
while(m+i < s.size()){
if(w[i] == s[m+i]){
if(i == w.size()-1) {
counter++;
res.push_back(m);
i = 0;
m++;
} else {
i++;
}
} else {
m = m + i - t[i];
if(t[i] > -1)
i = t[i];
else
i = 0;
}
}
return counter;
}
vector<int> createKMPTable(string str){
vector<int> table;
if(str.size() == 0)
return table;
table.push_back(-1);
if(str.size() == 1) {
return table;
}
table.push_back(0);
if(str.size() == 2) {
return table;
}
int i = 2;
int cnd = 0;
while( i < str.size() ) {
if(str[i-1] == str[cnd]){
table.push_back(++cnd);
i++;
} else if(cnd > 0){
cnd = table[cnd];
} else {
table.push_back(0);
i++;
}
}
return table;
}
int main(int argc, char** argv){
//variables
string w, s;
ifstream in;
//read
in.open("strmatch.in");
in >> w;
in >> s;
in.close();
//solve
int res = 0;
vector<int> matchVec;
vector<int> tKMP = createKMPTable(w);
if(w.size() < = s.size()) {
/*for(int i = 0; i < tKMP.size(); i++){
cout << tKMP[i];
}
cout << "\n";*/
res = match(s, w, tKMP, matchVec);
}
//write
ofstream out;
out.open("strmatch.out");
out << res << "\n";
for(int i = 0; i < matchVec.size(); i++){
out << matchVec[i] << " ";
}
out.close();
}