Pagini recente » Cod sursa (job #2509726) | Cod sursa (job #2496715) | Cod sursa (job #2739520) | Cod sursa (job #527573) | Cod sursa (job #1939995)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m,i,l,p[2000005],sol,v[1005];
char a[2000005],q,b[2000005];
int main()
{
fin >> a;
n = strlen (a);
for (i=n; i>=1; i--)
a[i] = a[i-1];
a[n+1] = 0;
fin >> b;
m = strlen (b);
for (i=m; i>=1; i--)
b[i] = b[i-1];
b[m+1] = 0;
l = 0;
p[0] = 0;
for (i=2; i<=n; i++)
{
while (l != 0 && a[i] != a[l+1])
l = p[l];
if (a[i] == a[l+1])
l++;
p[i] = l;
}
l = 0;
for (i=1; i<=m; i++)
{
while (l != 0 && b[i] != a[l+1])
l = p[l];
if (b[i] == a[l+1])
l++;
if (l == n)
{
sol++;
if (sol <= 1000)
v[sol] = i-n;
l = p[l];
}
}
fout << sol << "\n";
if (sol >= 1000)
sol = 1000;
for (i=1; i<=sol; i++)
fout << v[i] << " ";
return 0;
}