Pagini recente » Cod sursa (job #1396569) | Cod sursa (job #1043431) | Cod sursa (job #2821900) | Cod sursa (job #1042903) | Cod sursa (job #1492108)
#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);
int k = 0, i, match = 0;
for(i = 1;i < (int)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 < (int)t.size();++i) {
while(k > 0 && t[i] != s[k]) k = a[k-1];
if(t[i] == s[k]) k++;
if(k == (int)s.size()) {
if(match < 1000) v[match] = i - s.size() + 1;
match++;
k = a[k-1];
}
}
fout << match << '\n';
match = min(match, 1000);
for(int i = 0;i < match;++i)
fout<<v[i]<<" ";
}
int main()
{
string a ,b;
fin >> a >> b;
kmp(a, b);
return 0;
}