Pagini recente » Cod sursa (job #1420965) | Cod sursa (job #2711190) | Cod sursa (job #13374) | Cod sursa (job #2605507) | Cod sursa (job #2739247)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void kmp(string& s, int* lps) {
int k = 0, len = s.length();
lps[1] = 0;
for(int i = 2; i < len; i++) {
while(k && s[k + 1] != s[i]) k = lps[k];
if(s[k + 1] == s[i]) k++;
lps[i] = k;
}
}
const int NMAX = 2e6;
int lps[NMAX + 5];
string s, t;
int main()
{
fin >> s >> t; s = " " + s; t = " " + t;
kmp(s, lps);
int res = 0;
vector <int> sol;
int len = t.length(), k = 0, n = s.length() - 1; s += " ";
for(int i = 1; i < len; i++) {
while(k && s[k + 1] != t[i]) k = lps[k];
if(s[k + 1] == t[i]) k++;
if(k == n) {
res++;
if(res <= 1000) sol.push_back(i - n);
}
}
fout << res << "\n";
for(auto el : sol) fout << el << " ";
return 0;
}