Pagini recente » Cod sursa (job #543714) | Ședință 2014-10-XX | Cod sursa (job #1954536) | Cod sursa (job #673532) | Cod sursa (job #735558)
Cod sursa(job #735558)
#include <string>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 2000011
using namespace std;
string s, p;
vector< int > match;
int failureFunction[N_MAX];
int main()
{
int N, M, i, j, count=0;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
getline(in, p);
getline(in, s);
N=s.size(); M=p.size();
s.push_back(' '); p.push_back(' ');
for(i=2, j=0; i <= M; ++i)
{
for(; p[i-1] != p[j] && j; j=failureFunction[j]);
if(p[i-1] == p[j])
++j;
failureFunction[i]=j;
}
for(i=j=0; i < N; )
{
if(p[j] == s[i])
{
++i, ++j;
if(M == j)
{
++count;
if(count <= 1000)
match.push_back(i-M);
}
}
else if(j)
j=failureFunction[j];
else ++i;
}
out<<count<<'\n';
copy(match.begin(), match.end(), ostream_iterator<int>(out, " "));
out<<'\n';
return EXIT_SUCCESS;
}