Pagini recente » Sport | Cod sursa (job #2926727) | Cod sursa (job #50499) | Cod sursa (job #1443833) | Cod sursa (job #749489)
Cod sursa(job #749489)
#include <string>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
using namespace std;
const int N_MAX=2011;
const int MAX=1000;
int main()
{
string p, s;
vector<int> match;
int failureF[N_MAX];
int pSize, sSize, i, j, countMatch=0;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
getline(in, p);
getline(in, s);
pSize=p.size(), sSize=s.size();
failureF[0]=failureF[1]=0;
for(i=2, j=0; i <= pSize; ++i)
{
for(; p[i-1] != p[j] && j; j=failureF[j]);
if(p[i-1] == p[j])
++j;
failureF[i]=j;
}
p.push_back(' '); s.push_back(' ');
for(i=j=0; i < sSize; )
{
if(s[i] == p[j])
{
++i, ++j;
if(pSize == j)
{
++countMatch;
if(MAX >= countMatch)
match.push_back(i-pSize);
}
}
else if(j)
j=failureF[j];
else ++i;
}
out<<countMatch<<'\n';
copy(match.begin(), match.end(), ostream_iterator<int>(out, " "));
out<<'\n';
return EXIT_SUCCESS;
}