Pagini recente » Cod sursa (job #1680117) | Cod sursa (job #738215) | Cod sursa (job #746151) | Cod sursa (job #2490055) | Cod sursa (job #1815939)
#include <bits/stdc++.h>
using namespace std;
char s[4000005];
long long counter, raspuns[1001];
int z[4000005];
void Z_Algorithm (int lungime, int n)
{
z[1] = 0;
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)
raspuns[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 << raspuns[i] << " ";
return 0;
}