Pagini recente » Cod sursa (job #3251194) | Cod sursa (job #1492111)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void kmp(const string &s,const string &t) {
vector<int> a(s.size()), v(1000);
size_t k = 0, i, match = 0;
for(i = 1;i < s.size();++i) {
while(k > 0 && s[i] != s[k])
k = a[k - 1];
if(s[i] == s[k]) k++;
a[i] = k;
}
k = 0;
for(i = 0;i < t.size();++i) {
while(k > 0 && t[i] != s[k]) k = a[k-1];
if(t[i] == s[k]) k++;
if(k == s.size()) {
if(match < 1000) v[match++] = i + 1 - s.size();
else match++;
k = a[k-1];
}
}
fout << match << '\n';
match = min(match, (size_t)1000);
for(i = 0;i < match;++i)
fout << v[i] <<" ";
}
int main()
{
string a ,b;
fin >> a >> b;
kmp(a, b);
return 0;
}