Pagini recente » Cod sursa (job #1650780) | Cod sursa (job #275233) | Cod sursa (job #1139621) | Cod sursa (job #2926006) | Cod sursa (job #1070524)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
class StrMatcher {
public:
StrMatcher(const string &_W, const string &_S) :
S(_S),
W(_W),
m(-1)
{
computePartialMatchTable();
}
int getNextPos();
private:
void computePartialMatchTable();
int m,i;
string S;// The string in which we search
string W;// The string that is searched
vector<int> T;// Partial match table
};
void StrMatcher::computePartialMatchTable() {
int pos = 2;// current position that we are computing in t
int cnd = 0;// where in W is the next character of the current candidate
T.push_back(-1); T.push_back(0);
while(pos < W.size()) {
if(W[pos-1] == W[cnd]) {
cnd++;
T.push_back(cnd);
pos++;
}
else if(cnd > 0)
cnd = T[cnd];
else {
T.push_back(0);
pos++;
}
}
}
int StrMatcher::getNextPos() {
m++;
int i = 0;
while(m + i < S.size()) {
if(W[i] == S[m+i]) {
i++;
if(i == W.size()) {
return m;
}
}
else {
m += i - T[i];
if(T[i] > -1)
i = T[i];
else
i = 0;
}
}
return -1;
}
int main() {
string a,b;
in >> a >> b;
StrMatcher match(a,b);
vector<int> sol;
int pos = match.getNextPos();
while(pos != -1 && sol.size()<1000) {
sol.push_back(pos);
pos = match.getNextPos();
}
out << sol.size() << '\n';
for(size_t i = 0, n = sol.size(); i < n; ++i) {
out << sol[i] << ' ';
}
out << '\n';
return 0;
}