Pagini recente » Cod sursa (job #2209127) | Cod sursa (job #2724132) | Cod sursa (job #2560763) | Cod sursa (job #1195360) | Cod sursa (job #2756704)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
string A, B;
vector<int> prefix, ans;
void calculatePrefix()
{
int p = 0; // the size of the longest prefix that is also a suffix
for (int i = 2; i < A.size(); ++i) {
while (p && A[p + 1] != A[i])
p = prefix[p];
if (A[p + 1] == A[i])
++p;
prefix[i] = p;
}
}
int countMatches()
{
int p = 0;
int total = 0;
for (int i = 0; i < B.size(); ++i) {
while (p && A[p + 1] != B[i])
p = prefix[p];
if (A[p + 1] == B[i])
++p;
if (p == A.size() - 1) {
++total;
p = prefix[p];
if (ans.size() < 1000)
ans.emplace_back(i - (int)A.size() + 1);
}
}
return total;
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.sync_with_stdio(false);
fin.tie(0);
fin >> A >> B;
A = "#" + A;
B = "#" + B;
prefix.resize(A.size());
calculatePrefix();
fout << countMatches() << "\n";
for (auto it: ans)
fout << it << " ";
return 0;
}