Pagini recente » Cod sursa (job #549965) | Cod sursa (job #502019) | Cod sursa (job #1621306) | Cod sursa (job #1066015) | Cod sursa (job #1875695)
#include <fstream>
#include <vector>
#include <string.h>
#define VAL 4000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char P[VAL];
char T[VAL];
char TT[VAL];
int FF[VAL];
int n,i,r, L, x;
vector<int> v;
int main()
{
fin>>P;
fin>>T;
L=strlen(T);
TT[0]='\0';
strcat(TT,P);
strcat(TT,"*");
strcat(TT,T);
FF[0]=0;
n=strlen(TT);
for (i=1;i<n;i++)
{
r=FF[i-1];
while (r>0)
{
if (TT[r]==TT[i])
break;
else
r=FF[r-1];
}
if (TT[r]==TT[i])
FF[i]=1+r;
else
FF[i]=0;
}
r=strlen(P);
x=L+1;
for (i=n-1;i>n-1-L;i--)
{
x--;
if (FF[i]==r)
v.push_back(x-r);
}
fout << v.size() << '\n';
for (i=v.size()-1; i>=0; i--)
fout << v[i] << " ";
fin.close();
fout.close();
return 0;
}