Pagini recente » Cod sursa (job #2035565) | Cod sursa (job #1015355) | Cod sursa (job #2586587) | Cod sursa (job #483674) | Cod sursa (job #3321095)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s, t;
int n, m, i;
vector<int> rasp;
int lps[4000002];
static inline void Precalc() {
int j = 0;
for(int i = 1; i < n; i++) {
while(0 < j && t[i] != t[j]) j = lps[j - 1];
if(t[i] == t[j]) j++;
lps[i] = j;
}
}
int main() {
fin.tie(NULL);
fout.tie(NULL);
fin >> s >> t;
t = s + "#" + t;
n = t.size();
m = s.size();
Precalc();
for(i = 0; i < n; i++) {
//cout << lps[i] << " ";
if(m == lps[i]) {
rasp.push_back(i - m);
}
}
fout << rasp.size() << "\n";
for(i = 0; i < 1000 && i < rasp.size(); i++) {
fout << rasp[i] - m << " ";
}
return 0;
}