Pagini recente » Cod sursa (job #545664) | Cod sursa (job #1872238) | Cod sursa (job #540129) | Cod sursa (job #192492) | Cod sursa (job #1070949)
#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)
{
T.resize(W.size()+1,0);
computePartialMatchTable();
}
int getNextPos();
private:
void computePartialMatchTable();
int m;
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[0]=-1; T[1]=0;
while(pos < W.size()) {
if(W[pos-1] == W[cnd]) {
cnd++;
T[pos]=cnd;
pos++;
}
else if(cnd > 0)
cnd = T[cnd];
else {
T[pos]=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;
if(a.size()>b.size()){
out << "0\n";
return 0;
}
StrMatcher match(a,b);
vector<int> sol(1000,0);
int pos = match.getNextPos();
size_t n = 0;
while(pos != -1) {
if(n<1000)
sol[n]=pos;
n++;
pos = match.getNextPos();
}
out << n << '\n';
for(size_t i = 0, l = min(n,1000u); i < l; ++i) {
out << sol[i] << ' ';
}
out << '\n';
return 0;
}