Pagini recente » Cod sursa (job #2941415) | Cod sursa (job #1408133) | Cod sursa (job #1267032) | Cod sursa (job #1219978) | Cod sursa (job #1438982)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
string a, b;
// pi[i] the length of the greatest prefix of a(i-1) which is also a suffix for a
int pi[2000001];
vector<int> sol;
void prefix_function() {
int i, k = 0;
for (i = 1; i < a.size(); i++) {
while (k > 0 && a[i] != a[k]) {
k = pi[k-1];
}
if (a[i] == a[k]) {
k++;
}
pi[i] = k;
}
}
void match() {
int i, k = 0;
for (i = 0; i < b.size(); i++) {
while (k > 0 && b[i] != a[k]) {
k = pi[k-1];
}
if (b[i] == a[k]) {
k++;
if (k == a.size()) {
sol.push_back(i - a.size() + 1);
k = pi[k-1];
}
}
}
}
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> a >> b;
prefix_function();
match();
fout << sol.size() << "\n";
for (int i = 0; i < sol.size() && i < 1000; i++) {
fout << sol[i] << " ";
}
return 0;
}