Pagini recente » Cod sursa (job #1910799) | Cod sursa (job #419161) | Cod sursa (job #1558522) | Cod sursa (job #822019) | Cod sursa (job #1750048)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
vector <int> rez;
string a, b;
int pi[2000010];
void calc();
int main()
{
ifstream in("strmatch.in");
in >> a >> b;
a = "$" + a;
b = "$" + b;
while ((*a.rbegin() > 'z' || *a.rbegin() < 'a') && (*a.rbegin() > 'Z' || *a.rbegin() < 'A') && (*a.rbegin() > '9' || *a.rbegin() < '0'))
a.pop_back();
calc();
int q = 0;
for (int i = 1; i < b.size(); i++) {
while (q && a[q + 1] != b[i])
q = pi[q];
if (a[q + 1] == b[i])
q++;
if (q == a.size() - 1) {
rez.push_back(i - a.size() + 1);
q = pi[q];
}
}
ofstream out("strmatch.out");
out << (rez.size() < 1000 ? rez.size() : 1000) << '\n';
for (int i = 0; i < rez.size() && i < 1000; i++)
out << rez[i] << ' ';
in.close();
out.close();
return 0;
}
void calc()
{
pi[1] = 0;
int q = 0;
for (int i = 2; i < a.size(); i++) {
while (q && a[q + 1] != a[i])
q = pi[q];
if (a[q + 1] == a[i])
q++;
pi[i] = q;
}
}