Pagini recente » Cod sursa (job #1061375) | Cod sursa (job #2397807) | Cod sursa (job #1838960) | Istoria paginii runda/usor/clasament | Cod sursa (job #2346913)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string a, b;
vector <int> v, pot;
void prefix()
{
int n = a.size(), k = 0;
v.push_back(0);
for (int i = 2; i < n; i ++) {
while (k > 0 && a[k + 1] != a[i]) k = v[k];
if (a[k + 1] == a[i]) k ++;
v.push_back(k);
}
v.push_back(0);
}
void potrivire()
{
int n = a.size(), m = b.size(), q = 0;
for (int i = 1; i < m; i ++) {
while (q > 0 && a[q + 1] != b[i]) q = v[q];
if (a[q + 1] == b[i]) q ++;
if (q == n - 1) pot.push_back(i - n + 1);
}
}
int main()
{
fin >> a >> b;
prefix(), potrivire();
int n = pot.size();
fout << n << "\n";
for (int i = 0; i < n; i ++) fout << pot[i] << " ";
return 0;
}