Pagini recente » Cod sursa (job #1842147) | Cod sursa (job #2464091) | Cod sursa (job #2300348) | Cod sursa (job #2700523) | Cod sursa (job #2722924)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int prefix[2000001];
string a, b;
int main()
{
in >> a >> b;
a.insert(a.begin(), ' ');
b.insert(b.begin(), ' ');
for(int i = 2, lung = 0; i <= a.size() - 1; i++)
{
while(lung && a[lung + 1] != a[i])
lung = prefix[lung];
if(a[lung + 1] == a[i])
lung++;
prefix[i] = lung;
}
int nrSol = 0;
queue <int> sol;
for(int i = 1, lung = 0; i <= b.size() - 1; i++)
{
while(lung && a[lung + 1] != b[i])
lung = prefix[lung];
if(a[lung + 1] == b[i])
lung++;
if(lung == a.size() - 1)
{
sol.push(i - a.size() + 1);
lung = prefix[lung];
nrSol++;
}
}
out << nrSol << '\n';
for(int i = 1; i <= min(1000, nrSol); i++)
{
out << sol.front() << ' ';
sol.pop();
}
return 0;
}