Pagini recente » Cod sursa (job #1796208) | Cod sursa (job #1766768) | Istoria paginii utilizator/georgianamaxim | Cod sursa (job #550169) | Cod sursa (job #1830804)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
char sir1[2000005];
char sir2[2000005];
int sirx1[2000005];
int sirx2[2000005];
int lungime1 = 0;
int lungime2 = 0;
void citire()
{
fgets(sir1, 2000005, stdin);
sir1[strlen(sir1) - 1] = 0;
fgets(sir2, 2000005, stdin);
sir2[strlen(sir2) - 1] = 0;
lungime1 = strlen(sir1);
lungime2 = strlen(sir2);
}
void construire()
{
int x, y;
sirx1[0] = 0;
x = 0;
y = 1;
while(y < lungime1)
{
if(sir1[x] == sir1[y])
{
sirx1[y] = x + 1;
x++;
y++;
}
else
{
if(x == 0)
{
y++;
}
else
{
x = sirx1[x - 1];
while(x > 0)
{
if(sir1[x] != sir1[y])
{
x = sirx1[x - 1];
}
else
{
sirx1[y] = x + 1;
y++;
break;
}
}
}
}
}
// for(int i = 0; i < lungime1; i++)
// {
// printf("%d", sirx1[i]);
// }
}
void cautare()
{
int x, y;
x = 0;
y = 0;
int nr = 0;
vector<int> rez;
while(y < lungime2)
{
if(sir1[x] == sir2[y])
{
x++;
y++;
}
else
{
if(x != 0)
{
x = sirx1[x - 1];
}
else
{
y++;
}
}
if(x == lungime1)
{
nr++;
rez.push_back(y - lungime1);
}
}
printf("%d\n", nr);
int lim = nr;
if(lim > 1000)
{
lim = 1000;
}
for(int i = 0; i < lim; i++)
{
printf("%d ", rez[i]);
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
citire();
construire();
cautare();
return 0;
}