Pagini recente » Cod sursa (job #1892468) | Cod sursa (job #1893917) | Cod sursa (job #2884592) | Cod sursa (job #1922275) | Cod sursa (job #2222775)
#include <bits/stdc++.h>
using namespace std;
vector<int> P;
vector<int> answer;
string A, B;
int N, M;
void make_prefix()
{
int k = 0;
for (int i = 2; i <= N; ++i) {
while (k && A[k + 1] != A[i])
k = P[k];
k += (A[k + 1] == A[i]);
P[i] = k;
}
}
int make_match()
{
int total = 0;
int k = 0;
for (int i = 1; i <= M; ++i) {
while (k && A[k + 1] != B[i])
k = P[k];
k += A[k + 1] == B[i];
if (k == N) {
++ total;
if(answer.size() < 1000)
answer.emplace_back(i - N);
k = P[k];
}
}
return total;
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.sync_with_stdio(false);
fin.tie(0);
fin >> A >> B;
N = A.size();
M = B.size();
P.resize(N + 1);
A = "#" + A;
B = "#" + B;
make_prefix();
fout << make_match() << "\n";
for (auto it : answer)
fout << it << " ";
return 0;
}