Pagini recente » Cod sursa (job #601766) | Cod sursa (job #2177785) | Cod sursa (job #1235799) | Cod sursa (job #2877485) | Cod sursa (job #2375745)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main()
{
int w = -1;
string A, B;
in >> A >> B;
vector<int> sol;
vector<int> pi(A.size() + 1);
pi[0] = -1;
for (int i = 1; i < A.size(); i++)
{
while (w != -1 && A[w + 1] != A[i])
w = pi[w];
if (A[w + 1] == A[i])
w++;
pi[i] = w;
}
w = -1;
for (int i = 0; i < B.size(); i++)
{
while (w != -1 && A[w + 1] != B[i])
w = pi[w];
if (A[w + 1] == B[i])
w++;
if (w == A.size() - 1)
{
sol.push_back(i - A.size() + 1);
w = pi[w];
}
}
int Size = sol.size();
out << Size << '\n';
for (int i = 0; i < min(Size, 1000); i++)
out << sol[i] << ' ';
return 0;
}