Pagini recente » Arhiva de probleme | Cod sursa (job #2229328) | Cod sursa (job #2442746) | Cod sursa (job #976764) | Cod sursa (job #1070964)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;
class StrMatcher {
public:
StrMatcher() :
m(-1)
{
T.resize(a.size()+1,0);
computePartialMatchTable();
}
int getNextPos();
private:
void computePartialMatchTable();
int m;
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 < a.size()) {
if(a[pos-1] == a[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 < b.size()) {
if(a[i] == b[m+i]) {
i++;
if(i == a.size()) {
return m;
}
}
else {
m += i - T[i];
if(T[i] > -1)
i = T[i];
else
i = 0;
}
}
return -1;
}
int main() {
a.reserve(2000002);
b.reserve(2000002);
in >> a >> b;
if(a.size()>b.size()){
out << "0\n";
return 0;
}
StrMatcher match;
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;
}