Pagini recente » Cod sursa (job #618443) | Cod sursa (job #2205916) | Cod sursa (job #1075998) | Cod sursa (job #2245971) | Cod sursa (job #2909460)
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;
int main()
{
ifstream fin; fin.open("strmatch.in");
ofstream fout; fout.open("strmatch.out");
string A, B;
fin >> A >> B;
int count, i, j;
vector <int> vec(A.length()+1, 0);
vector <int> rs;
j = 0;
i = 1;
while (i < A.length()) {
if (A[i] == A[j]) {
j++;
vec[i] = j;
i++;
}
else // (pat[i] != pat[len])
{
// This is tricky. Consider the example.
// AAACAAAA and i = 7. The idea is similar
// to search step.
if (j != 0) {
j = vec[j - 1];
// Also, note that we do not increment
// i here
}
else // if (len == 0)
{
vec[i] = 0;
i++;
}
}
}
for (i=0, j=0;i<B.length();)
{
if (B[i]==A[j])
{
i++;
j++;
}
if (j==A.length()) count++, rs.push_back(i-j), j=vec[j-1];
else if (B[i]!=A[j]) {
if (j!=0) j=vec[j-1];
else i++;
}
}
fout << count << "\n";
for (auto c:rs) fout << c << " ";
fin.close();
fout.close();
}