Pagini recente » Cod sursa (job #2516221) | Cod sursa (job #967427) | Cod sursa (job #2506153) | Cod sursa (job #2128586) | Cod sursa (job #1675600)
#include <fstream>
#define DMAX 2000010
#define MAX 1000
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
void citire();
void rez();
void afisare();
inline int minim(int, int);
int m, n;
char sir1[DMAX], sir2[DMAX];
int prec[DMAX];
int nrsol, sol[MAX+10];
int main()
{
citire();
rez();
afisare();
fin.close();
fout.close();
return 0;
}
void citire()
{
fin.getline(sir2+1, DMAX);
m=(int)strlen(sir2+1);
fin.getline(sir1+1, DMAX);
n=(int)strlen(sir1+1);
}
void rez()
{
int a, b, i, x;
//prima parte
prec[1]=0;
a=0;
for (b=2; b<=m; b++)
{
while (a>0 && sir2[a+1]!=sir2[b])
a=prec[a];
if (sir2[a+1]==sir2[b])
a=a+1;
prec[b]=a;
}
//a doua parte
x=0;
for (i=1; i<=n; i++)
{
while (x>1 && sir2[x+1]!=sir1[i])
x=prec[x];
if (sir2[x+1]==sir1[i]) x++;
if (x==m)
{
nrsol++;
if (nrsol<=MAX) sol[nrsol]=i-m+1;
//fout<< i-m+1<< '\n';
x=prec[x];
}
}
}
void afisare()
{
int i, x=minim(nrsol, MAX);
fout<< nrsol<< '\n';
for (i=1; i<=x; i++)
fout<< sol[i]-1<< ' ';
}
inline int minim(int a, int b)
{
if (a<b) return a;
return b;
}