Pagini recente » Cod sursa (job #2734612) | Cod sursa (job #2591483)
#include <fstream>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s, w;
//folosim algoritmul KMP
int t[2000001], n, m;
//t[i] = lungimea celui mai lung prefix al lui w, astfel incat acesta sa fie sufix al lui a[0...i]; t[i] != i (adica nu pot avea prefix = sufix)
void precalc()
{
t[0] = 0;
int k = -1, i;
for (i = 1; i<w.size(); i++)
{
while (k > 0 && w[k+1] != w[i])
k = t[k];
if (w[k+1] == w[i])
k++;
t[i] = k;
}
}
int ap[1001];
int main()
{
fin >> w >> s;
int i, k = -1;
for (i = 0; i<s.size(); i++)
{
while (k > 0 && s[i] != w[k+1])
k = t[k]; //adica imi misca w si imi incearca toate deplasamentele posibile
if (s[i] == w[k+1])
k++;
if (k+1 == w.size())
{
ap[0]++;
if (ap[0] <= 1000)
ap[ap[0]] = i-k;
k = t[k];
}
}
fout << ap[0] << '\n';
for (i = 1; i<=min(ap[0], 1000); i++)
fout << ap[i] << ' ';
return 0;
}