Pagini recente » Cod sursa (job #1125039) | Cod sursa (job #549710) | Cod sursa (job #2804411) | Cod sursa (job #412149) | Cod sursa (job #2117665)
#include <fstream>
#include <cstdio>
#include <string.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char v[4000005];
long long counter, raspuns[1001];
int z[4000005];
void z_alg(int n, int lungime)
{
int l = 1, r = 1;
for ( int i = 2; i <= n; ++i )
{
if ( i > r )
{
while ( z[i]+i <= n && v[z[i]+i] == v[z[i]+1]) z[i]++;
l = i;
r = z[i]+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 && v[z[i]+i] == v[z[i]+1] ) z[i]++;
l = i;
r = z[i]+i-1;
}
}
if ( z[i] == lungime )
{
counter++;
if ( counter <= 1000 ) raspuns[counter] = i-lungime-2;
}
}
}
int main()
{
int n, len;
fin>>(v+1);
len = strlen(v+1);
v[len+1] = '#';
fin>>(v+len+2);
n = strlen(v+1);
z_alg(n, len);
fout<<counter<<'\n';
for ( int i = 1; i <= counter; ++i )
fout<<raspuns[i]<<" ";
}