Pagini recente » Cod sursa (job #155364) | Autentificare | Cod sursa (job #874889) | Cod sursa (job #171544) | Cod sursa (job #2345947)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string sir, model;
vector <int> urm, ans;
int n, m;
void Prefix()
{
int i = 1, j = 0;
urm.push_back(0);
while (i < m)
{
if (model[i] == model[j])
{
j++;
urm.push_back(j);
i++;
}
else
{
if (j > 0)
j = urm[j - 1];
else
{
urm.push_back(0);
i++;
}
}
}
}
void KMP()
{
int i = 0, j = 0;
while (i < n)
{
if (sir[i] == model[j])
{
i++;
j++;
}
if (j == m)
{
ans.push_back(i - j);
j = urm[j - 1];
}
if (i < n && sir[i] != model[j])
{
if (j > 0)
j = urm[j - 1];
else
i++;
}
}
}
int main()
{
fin >> model >> sir;
n = sir.size();
m = model.size();
Prefix();
KMP();
fout << ans.size() << "\n";
for (int i = 0; i < (ans.size() > 1000 ? 1000 : ans.size()); i++)
fout << ans[i] << " ";
return 0;
}