Pagini recente » Cod sursa (job #2642700) | Cod sursa (job #3201057) | Cod sursa (job #1941509) | Cod sursa (job #891055) | Cod sursa (job #820573)
Cod sursa(job #820573)
// bullcrap code, chaos
#include <string>
#include <iostream>
#include <vector>
using namespace std;
vector<int> prf;
int kmp(string n, string m)
{
int ln = n.size();
int lm = m.size();
int k;
prf.resize(ln);
prf[0] = -1;
k = -1;
for (int i = 1; i < ln; ++i)
{
while (k > -1 && n[k + 1] != n[i])
k = prf[k];
if (n[k + 1] == n[i])
++k;
prf[i] = k;
}
k = -1;
for (int i = 0; i < lm; ++i)
{
while (k > -1 && n[k + 1] != m[i])
k = prf[k];
if (n[k + 1] == m[i])
++k;
if (k == ln - 1)
{
return i - k;
}
}
return -1;
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string n, m;
int i, r;
int v[1000];
cin >> n >> m;
for (r = 0, i = 0; i < 1000; ++i)
{
r = kmp(n, m);
if (r == -1) break;
v[i] = r;
m = m.substr(r + 1);
}
cout << i << endl;
int p = 0;
for (int j = 0; j < i; ++j)
{
if (j == 0)
{
cout << v[j] << " ";
p = v[j];
}
else
{
p += v[j] + 1;
cout << p << " ";
}
}
fclose(stdin);
return 0;
}