Pagini recente » Cod sursa (job #375569) | Cod sursa (job #456790) | Statistici Balu Cristian (balucristian) | Cod sursa (job #381108) | Cod sursa (job #2017113)
#include <bits/stdc++.h>
using namespace std;
const int maxlen = 4e6 + 20;
char s[maxlen];
int z[maxlen];
int cnt = 0;
int ans[1010];
void Zalg(int len, int n){
z[1] = 0;
int l = 1, r = 1;
for(int i = 2; i <= n; ++i){
if(i > r){
while(z[i]+i <= n && s[z[i]+i] == s[z[i]+1]) ++z[i];
l = i;
r = i + z[i] - 1;
}
else {
z[i] = min(r-i, z[i-l+1]);
while(z[i]+i <= n && s[z[i]+i] == s[z[i]+1]) ++ z[i];
if(z[i] + i - 1 > r){
l = i;
r = i + z[i]-1;
}
}
if(z[i] == len){
if(cnt < 1000){
ans[cnt] = i - len - 2;
}
++cnt;
}
}
}
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int main()
{
f >> (s+1);
int len = strlen(s+1);
s[len+1] = '#';
f >> (s+len+2);
int n = strlen(s + 1);
Zalg(len, n);
g << cnt << '\n';
for(int i = 0; i < cnt && i < 1000; ++i){
g << ans[i] << ' ';
}
return 0;
}