Pagini recente » Cod sursa (job #1070026) | Cod sursa (job #2588397) | Cod sursa (job #807939) | Cod sursa (job #494992) | Cod sursa (job #1984826)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
vector<int> KMP(const string &s, const string &pattern)
{
vector<int> ret;
if(s.size() < pattern.size())
return ret;
vector<int> pi;
pi.resize(pattern.size());
pi[0] = 0;
int pos = 0;
for(int i = 1; i < pattern.size(); ++i)
{
pos = pi[i-1];
while(pos != 0 && pattern[i] != pattern[pos])
pos = pi[pos - 1];
if(pattern[i] == pattern[pos])
pos++;
pi[i] = pos;
}
vector<int> d;
d.resize(s.size());
if(s[0] == pattern[0])
d[0] = 1;
for(int i = 1; i < s.size(); ++i)
{
pos = d[i-1];
while(pos != 0 && s[i] != pattern[pos])
pos = pi[pos - 1];
if(s[i] == pattern[pos])
pos++;
d[i] = pos;
if(pos == pattern.size())
ret.push_back(i - pos + 1);
}
return ret;
}
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a, b;
in >> a >> b;
vector<int> sol = KMP(b, a);
out << sol.size() << "\n";
for(int i = 0; i < sol.size() && i < 1000; ++i)
out << sol[i] << " ";
in.close();
out.close();
return 0;
}