Pagini recente » Cod sursa (job #1873261) | Cod sursa (job #1009729) | Cod sursa (job #2226931) | Cod sursa (job #796559) | Cod sursa (job #1212431)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char a[2000010],b[2000010];
int z[2000010],pr[1010],cnt,t;
void calc_z ()
{
z[1] = 0;
int L = 0, R = 0, n = strlen (a+1);
for (int i=2; i <= n; ++i)
{
if (i > R)
{
int j=1;
L = i;
R = i;
while (R <= n && a[R] == a[j])
{
++j;
++R;
}
--R;
z[i] = j-1;
}
else
{
if (z[i-L+1] < R-i+1)
z[i] = z[i-L+1];
else
{
int j = R-i+1;
L = i;
while (R <= n && a[R] == a[j])
{
++j;
++R;
}
--R;
z[i] = j-1;
}
}
}
}
void solve ()
{
int L = 0, R = 0, n = strlen (b+1), na = strlen (a+1);
for (int i=1; i<=n; ++i)
{
int ans = 0;
if (i > R)
{
int j = 1;
L = i;
R = i;
while (R <= n && b[R] == a[j])
{
++j;
++R;
}
--R;
ans = j-1;
}
else
{
if (z[i-L+1] < R-i+1)
ans = z[i-L+1];
else
{
int j = R-i+1;
L = i;
while (R <= n && b[R] == a[j])
{
++j;
++R;
}
--R;
ans = j-1;
}
}
if (ans == na)
{
++cnt;
if (cnt < 1000)
pr[++t] = i;
}
}
}
void read ()
{
fin>>a+1>>b+1;
}
void print ()
{
fout<<cnt<<"\n";
for (int i=1; i<=t; ++i)
fout<<pr[i]-1<<" ";
}
int main()
{
read ();
calc_z ();
solve ();
print ();
}