Pagini recente » Cod sursa (job #719063) | Cod sursa (job #2276291) | Cod sursa (job #2908261) | Cod sursa (job #189873) | Cod sursa (job #1168576)
#include<fstream>
#include<string>
#include<algorithm>
using namespace std;
string A, B;
int esec[2000001], i, k, sol[1005], nrSol=0;
void makeprefix()
{
esec[0] = -1;
for (i = 1; i < A.size(); i++)
{
k = i - 1;
while (k > 0 && A[esec[k] + 1] != A[i])
k = esec[k];
esec[i] = esec[k] + 1;
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
getline(fin, A);
getline(fin, B);
A = ' ' + A;
k = 0;
for (i = 1; i < B.size(); i++)
{
while (k>0 && (A[k+1] != B[i]))
k = esec[k];
if (B[i] == A[k + 1])
k++;
if (k == A.size() - 1)
{
nrSol++;
if (nrSol <= 1000)
sol[nrSol] = i - (A.size() - 1);
k = esec[k];
}
}
fout<<nrSol << "\n";
for (i = 1; i <= min(nrSol, 1000); i++)
fout << sol[i] << " ";
}