Pagini recente » Cod sursa (job #2138663) | Cod sursa (job #26190) | Cod sursa (job #1520411) | Cod sursa (job #1679187) | Cod sursa (job #1758675)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
string a, b;
int r = 0;
vector <int> rez;
int pi[2000010];
void pref();
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> a >> b;
pref();
int k = 0;
for (int i = 0; i < b.size(); i++) {
while (a[k + 1] != b[i] && k > 0)
k = pi[k];
if (a[k + 1] == b[i]) {
k++;
if (k == a.size() - 1) {
k = pi[k];
r++;
rez.push_back(i - a.size() + 2);
}
}
}
out << r << '\n';
for (int i = 0; i < 1000 && i < rez.size(); i++)
out << rez[i] << ' ';
return 0;
}
void pref()
{
a = "$" + a;
int k = 0;
for (int i = 2; i < a.size(); i++) {
while (k != 0 && a[i] != a[k + 1])
k = pi[k];
if (a[i] == a[k + 1])
pi[i] = ++k;
}
}