Pagini recente » Cod sursa (job #3038963) | Cod sursa (job #327066) | Cod sursa (job #1365090) | Cod sursa (job #2530869) | Cod sursa (job #2009629)
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
char s[2000002];
long long counter, answer[1001];
int z[2000002];
void z_algorithm (int lungime, int n)
{
int l, r;
l = 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
{
if ( i + z[i-l+1] - 1 < r)
z[i] = z[i-l+1];
else
{
z[i] = r-i;
while ( z[i] + i <= n && s[z[i]+i] == s[z[i]+1])
z[i]++;
l = i;
r = i + z[i] - 1;
}
}
if ( z[i] == lungime )
{
++counter;
if ( counter <= 1000 )
answer[counter] = i - lungime - 2;
}
}
}
int main()
{
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
int n, i, len;
cin>>(s+1);
len = strlen(s+1);
s[len+1] = '#';
cin>>(s+len+2);
n = strlen(s+1);
z_algorithm(len, n);
cout<<counter<<'\n';
for ( int i = 1; i<=counter && i<=1000; ++i )
cout<<answer[i]<<" ";
}