Pagini recente » Cod sursa (job #748525) | Cod sursa (job #2252992) | Cod sursa (job #1796884) | Cod sursa (job #1132528) | Cod sursa (job #3188575)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, pi[4000002], i, j;
string p, s;
queue<int> q;
static inline void CalcPi() {
pi[0] = 0;
j = 0;
for(i = 1; i < m; i++) {
while(j != 0 && p[i] != p[j]) j = pi[j - 1];
if(p[i] == p[j]) j++;
pi[i] = j;
}
}
static inline void Cauta() {
j = 0;
for(i = 0; i < n; i++) {
while(j != 0 && p[j] != s[i]) j = pi[j - 1];
if(p[j] == s[i]) j++;
if(j == m && q.size() < 1000) q.push(i - m + 1);
}
}
int main() {
fin >> p >> s;
n = s.size();
m = p.size();
CalcPi();
Cauta();
fout << q.size() << "\n";
while(!q.empty()) {
fout << q.front() << " ";
q.pop();
}
return 0;
}