Pagini recente » Cod sursa (job #1865679) | Cod sursa (job #312515) | Cod sursa (job #2038439) | Cod sursa (job #78617) | Cod sursa (job #2849715)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int maxN = 4e6 + 5;
int lps[maxN];
void kmp (string s) {
for(int i = 1; i < s.size(); ++i) {
int j = lps[i-1];
while(j > 0 && s[i] != s[j])
j = lps[j-1];
if(s[i] == s[j])
j++;
lps[i] = j;
}
}
int main() {
string a; fin >> a;
string b; fin >> b;
string s = a + '&' + b;
kmp(s);
vector <int> ans;
for(int i = a.size() + 1; i < s.size(); ++i)
if(lps[i] == a.size())
ans.push_back(i - (a.size() + 1));
fout << ans.size() << "\n";
for(int i = 0; i < min(1000, (int) ans.size()); ++i)
fout << ans[i] - a.size() + 1<< " ";
return 0;
}