Pagini recente » Cod sursa (job #1557853) | Cod sursa (job #1238911) | Cod sursa (job #1274297) | Cod sursa (job #775951) | Cod sursa (job #2922199)
#include <fstream>
#include <cstring>
#define N_MAX 2000010
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s[N_MAX], pattern[N_MAX];
int n, m, i, cnt, pz, top, p[N_MAX], sol[N_MAX];
int main()
{
ios::sync_with_stdio(false);
f.tie(0), g.tie(0);
f >> (pattern + 1) >> (s + 1);
n = strlen(pattern + 1);
m = strlen(s + 1);
for (i = 2; i <= n; ++i)
{
if (pattern[cnt + 1] == pattern[i])
{
while (i <= n && pattern[cnt + 1] == pattern[i])
{
p[i] = ++cnt;
++i;
}
--i;
}
cnt = 0;
}
pz = 1;
for (i = 1; i <= m; ++i)
if (s[i] == pattern[pz])
{
while (pz <= n && i <= m && s[i] == pattern[pz])
++pz, ++i;
if (pz > n)
{
sol[++top] = i - n - 1;
if (top == 1000)
break;
}
--pz; --i;
(p[pz]) ? pz = p[pz] : pz = 1;
--i;
}
g << top << '\n';
for (i = 1; i <= min(top, 1000); ++i)
g << sol[i] << " ";
return 0;
}