Pagini recente » Cod sursa (job #3323621) | Cod sursa (job #1811917) | Cod sursa (job #1261472) | Cod sursa (job #1260775) | Cod sursa (job #1771028)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int ct=0;
string p, t;
vector<int> prefix_function (string Z) {
int n = (int) Z.length();
vector<int> F (n);
F[0]=0;
for (int i=1; i<n; ++i) {
int j = F[i-1];
while (j > 0 && Z[i] != Z[j])
j = F[j-1];
if (Z[i] == Z[j]) ++j;
F[i] = j;
if(F[i]==p.size())
ct++;
}
return F;
}
int main()
{
string a;
fin >> p >> t;
a=p+"#"+t;
vector<int> b(a.size());
b = prefix_function(a);
fout << ct << '\n';
for(int i=0; i<b.size(); i++)
{
if(b[i]==p.size())
{
fout << i-2*p.size() << ' ';
}
}
return 0;
}