Pagini recente » Cod sursa (job #3032489) | Cod sursa (job #1133470) | Cod sursa (job #498331) | Cod sursa (job #2661943) | Cod sursa (job #1646759)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
char text[2000200];
char cuvant[2000200];
int repetare[2000200];
int contor = 0;
void citire()
{
fgets(cuvant, 2000200, stdin);
fgets(text, 2000200, stdin);
text[strlen(text) - 1] = 0;
cuvant[strlen(cuvant) - 1] = 0;
}
void generareRepetare()
{
int l = strlen(cuvant);
int j = 0;
for(int i = 1; i < l; i++)
{
while(j > 0 && cuvant[j] != cuvant[i])
{
j = repetare[j - 1];
}
if(cuvant[j] == cuvant[i])
{
j++;
}
repetare[i] = j;
//printf("%d ", repetare[i]);
}
}
vector<int> solutii;
bool ok = false;
int nr = 0;
void parcurgere()
{
int l = strlen(text);
int j = 0;
// for(int i = 0; i < l; i++)
// {
// while(true)
// {
// if(text[i] == cuvant[j])
// {
// j++;
//
// if(j == strlen(cuvant))
// {
// nr++;
// contor++;
// if(contor <= 1000)
// {
// solutii.push_back(i + 1 - strlen(cuvant));
// j = repetare[j - 1];
// }
// }
// break;
// }
// else if(j != 0)
// {
// j = repetare[j - 1];
// }
//
// if(j == 0)
// {
// break;
// }
// }
// }
int i = 0;
while(true)
{
if(i == l)
{
break;
}
if(text[i] == cuvant[j])
{
i++;
j++;
if(j == strlen(cuvant))
{
nr++;
contor++;
if(contor <= 1000)
{
solutii.push_back(i - strlen(cuvant));
j = repetare[j - 1];
}
}
}
else if(j > 0)
{
j = repetare[j - 1];
}
else
{
i++;
}
}
}
void afisare()
{
printf("%d\n", nr);
if(nr > 1000)
{
nr = 1000;
}
for(int i = 0; i < nr; i++)
{
printf("%d ", solutii[i]);
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
citire();
generareRepetare();
parcurgere();
afisare();
return 0;
}