Pagini recente » Cod sursa (job #2028669) | Cod sursa (job #444813) | Cod sursa (job #1729278) | Cod sursa (job #2922968) | Cod sursa (job #2304508)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A, B, C;
int patternSize, Z[4000005];
void CalculateZ()
{
int st = 0, dr = 0;
for(int i = 1; i < C.size(); i++)
if(i > dr)
{
st = dr = i;
while(dr < C.size() && C[dr] == C[dr - st])
dr++;
Z[i] = dr - st;
dr--;
}
else
{
if(Z[i - st] < dr - i + 1)
Z[i] = Z[i - st];
else
{
st = i;
while(dr < C.size() && C[dr] == C[dr - st])
dr++;
Z[i] = dr - st;
dr--;
}
}
}
int main()
{
fin >> A >> B;
for(int i = 0; i < A.size(); i++)
C += A[i];
C += '0';
for(int i = 0; i < B.size(); i++)
C += B[i];
patternSize = A.size(); A.clear(); B.clear();
CalculateZ();
int nsol = 0;
vector <int> sol;
for(int i = 0; i < C.size(); i++)
if(Z[i] == patternSize)
{
nsol++;
if(sol.size() < 1000)
sol.push_back(i - patternSize - 1);
}
fout << nsol << '\n';
for(auto it : sol)
fout << it << ' ';
return 0;
}