Pagini recente » Cod sursa (job #1154139) | Cod sursa (job #1108294) | Cod sursa (job #1184140) | Cod sursa (job #171376) | Cod sursa (job #311521)
Cod sursa(job #311521)
#include <fstream>
#include <string>
#include <iterator>
#include <vector>
using namespace std;
#define NUME "strmatch"
ifstream fi(NUME".in");
ofstream fo(NUME".out");
#define MAXN 2000001
string A, B;
int pi[MAXN];
void build(string str) {
int i;
pi[0] = -1;
for (i = 1; i <= str.size(); ++i) {
pi[i] = pi[i-1] + 1;
while (pi[i] > 0 && str[i-1] != str[pi[i]-1])
pi[i] = pi[pi[i] - 1] + 1;
}
}
int main()
{
vector<int> occ;
int i, j;
fi >> B >> A; // B = pattern
build(B);
for (i = 0, j = 0; i < A.size(); ++i) {
while (j && A[i] != B[j])
j = pi[j];
if (A[i] == B[j])
++j;
if (j == B.size()) {
if (occ.size() < 1000)
occ.push_back(i-j+1);
j = pi[j];
}
}
fo << occ.size() << "\n";
copy(occ.begin(), occ.end(), ostream_iterator<int>(fo, " "));
return 0;
}