Pagini recente » Cod sursa (job #3288554) | Rating Chiriluta George-Stefan (ChiriGeorge) | Cod sursa (job #1188808) | Cod sursa (job #3281479) | Cod sursa (job #806948)
Cod sursa(job #806948)
#include <string>
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iterator>
#include <algorithm>
using namespace std;
const int NMAX = 2000011;
int countMatches;
int errorF[NMAX];
vector<int> matches;
inline int _min(int x, int y) {return x <= y ? x : y;}
void computeErrorF(string pattern)
{
int M, i, j;
M = pattern.size();
for(i = 2, j = 0; i <= M; ++i)
{
for(; pattern[i-1] != pattern[j] && j; j = errorF[j]);
if(pattern[i-1] == pattern[j]) ++j;
errorF[i] = j;
}
}
void findPattern(string s, string pattern)
{
int N, M, i, j;
N = s.size();
M = pattern.size();
pattern.push_back(' ');
computeErrorF(pattern);
for(i = j = 0; i < N; )
{
if(s[i] == pattern[j])
{
++i, ++j;
if(M == j)
{
++countMatches;
if(1000 >= countMatches) matches.push_back(i-M);
}
}
else if(0 != j)
{
j = errorF[j];
}
else {
++i;
}
}
pattern.erase(pattern.end()-1);
}
int main()
{
string s, pattern;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
getline(in, pattern);
getline(in, s);
findPattern(s, pattern);
out << countMatches << '\n';
copy(matches.begin(), matches.end(), ostream_iterator<int>(out, " "));
}