Pagini recente » Cod sursa (job #2840729) | Cod sursa (job #462755) | Borderou de evaluare (job #1257141) | Borderou de evaluare (job #2383044) | Cod sursa (job #2393782)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int VAL=4000005;
int N, M, i, j, Z[VAL];
int L, R, poz, ANS;
string S, T;
vector <int> SOL;
int main()
{
fin >> S >> T;
N=S.size();
M=T.size();
S='*'+S+'*'+T+'*';
for (i=2; i<=N+M+1; i++)
{
if (S[i]!=S[1])
{
Z[i]=0;
continue;
}
if (i>R)
{
Z[i]=1;
while (S[1+Z[i]]==S[i+Z[i]])
Z[i]++;
L=i;
R=i+Z[i]-1;
}
else
{
poz=i-L+1;
Z[i]=min(Z[poz], R-i+1);
while (S[1+Z[i]]==S[i+Z[i]])
Z[i]++;
if (i+Z[i]-1>R)
{
L=i;
R=i+Z[i]-1;
}
}
if (Z[i]==N)
{
ANS++;
if (ANS<=1000)
SOL.push_back(i-N-2);
}
}
fout << ANS << '\n';
for (i=0; i<SOL.size(); i++)
fout << SOL[i] << " ";
fin.close();
fout.close();
return 0;
}