Pagini recente » Cod sursa (job #2094407) | Cod sursa (job #36990) | Cod sursa (job #665741) | Cod sursa (job #52680) | Cod sursa (job #2224378)
//2
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int maxn = 2e6+5;
string p, t;
int prefix[maxn];
int rez[maxn], rezk;
int n, m;
void prefix_calculate()
{
int a = 0, i = 0;
prefix[1] = 0;
for(i = 2; i <= n; i ++)
{
while(a > 0 && p[a+1] != p[i])
a = prefix[a];
if(p[a+1] == p[i])
++a;
prefix[i] = a;
}
}
void kmp_calculate()
{
int i = 1, j = 1, k = 1;
while(m - k + 1 >= n)
{
while(j <= n && t[i] == p[j]){
i ++;
j ++;
}
if(j > n)
rez[++rezk] = k;
if(prefix[j-1] > 0)
k = i - prefix[j-1];
else
{
if(i == k) i++;
k = i;
}
if(j > 1)
j = prefix[j-1] + 1;
}
}
int main()
{
f >> p;
f >> t;
p = " " + p;
n = p.size() - 1;
t = " " + t;
m = t.size() - 1;
prefix_calculate();
kmp_calculate();
g << rezk << '\n';
int file_size = min(rezk, 1000);
for(int i = 1; i <= file_size; i ++)
g << rez[i]-1 << ' ';
return 0;
}