Pagini recente » Cod sursa (job #881600) | Cod sursa (job #3247821) | Cod sursa (job #2546842) | Cod sursa (job #1281991) | Cod sursa (job #1116794)
/* z-algorithm */
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <vector>
#define NM 2000010
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char Pattern[NM], Text[NM];
int N, M, ANS;
int Z[NM], Match[NM];
vector<int> Poz;
void Read ()
{
f >> (Pattern+1);
N=strlen(Pattern+1);
f >> (Text+1);
M=strlen(Text+1);
f.close();
}
void BuildZ ()
{
int C=1, R=0;
for (int i=2; i<=N; i++)
{
if (i<=R)
Z[i]=min(Z[i-C+1], R-i+1);
while (i+Z[i]<=N && Pattern[i+Z[i]]==Pattern[1+Z[i]])
Z[i]++;
if (i+Z[i]-1>R)
{
C=i;
R=i+Z[i]-1;
}
}
}
void Solve ()
{
int C=1, R=0;
int lun=0;
for (int i=1; i<=M; i++)
{
if (i<=R)
lun=min(Z[i-C+1], R-i+1);
while (1+lun<=N && i+lun<=M && Pattern[1+lun]==Text[i+lun])
lun++;
if (lun==N && ANS<1000)
{
ANS++;
Poz.push_back(i-1);
}
if (i+lun-1>R)
{
C=i;
R=i+lun-1;
}
}
}
void Print ()
{
g << ANS << '\n';
for (size_t i=0; i<Poz.size(); i++)
g << Poz[i] << ' ';
g << '\n';
g.close();
}
int main ()
{
Read();
BuildZ();
Solve();
Print();
return 0;
}