Pagini recente » Cod sursa (job #1105602) | Cod sursa (job #1046157) | Cod sursa (job #1821715) | Istoria paginii runda/dorel | Cod sursa (job #2053551)
#include <fstream>
#include <vector>
#define VAL 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int N, M, i, j, K;
int Z[VAL], L, R;
string P, T;
vector <int> SOL;
int main()
{
fin >> P >> T;
M=P.size();
P='*'+P+'*'+T;
N=P.size();
Z[1]=0;
L=R=1;
for (i=2; i<N; i++)
{
if (P[i]!=P[1])
Z[i]=0;
else
{
if (i>R)
{
Z[i]=1;
while (P[i+Z[i]]==P[1+Z[i]])
Z[i]++;
L=i;
R=i+Z[i]-1;
}
else
{
Z[i]=min(Z[i-L+1], R-i+1);
while (P[i+Z[i]]==P[1+Z[i]])
Z[i]++;
if (i+Z[i]-1>R)
{
L=i;
R=i+Z[i]-1;
}
}
}
if (Z[i]==M)
{
K++;
if (K<=1000)
SOL.push_back(i-M-2);
}
}
fout << K << '\n';
for (i=0; i<SOL.size(); i++)
fout << SOL[i] << " ";
fin.close();
fout.close();
return 0;
}