Pagini recente » Cod sursa (job #2157988) | Cod sursa (job #1016318) | Cod sursa (job #3223760) | Cod sursa (job #385981) | Cod sursa (job #2210760)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int NMAX = 2000005;
string target, s;
int kmp[NMAX];
int main() {
cin >> target;
cin >> s;
target = " " + target;
s = " " + s;
int k = 0;
for(int i = 2; i < target.size(); i ++) {
while(k > 0 && target[k + 1] != target[i])
k = kmp[k];
if(target[k + 1] == target[i])
k ++;
kmp[i] = k;
}
k = 0;
vector<int> sol;
for(int i = 1; i < s.size(); i ++) {
while(k > 0 && target[k + 1] != s[i])
k = kmp[k];
if(target[k + 1] == s[i])
k ++;
if(k == target.size() - 1) {
k = kmp[k];
sol.push_back(i - (target.size() - 1));
}
}
cout << sol.size() << "\n";
for(int i = 0; i < sol.size(); i ++)
if(i < 1000)
cout << sol[i] << " ";
return 0;
}