Pagini recente » Cod sursa (job #2946264) | Cod sursa (job #2164510) | Cod sursa (job #186107) | Cod sursa (job #2578251) | Cod sursa (job #2979734)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 2e6;
int pi[2*nmax+5];
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string n, m; f >> n >> m;
int temp = n.size() + 1;
n = n + "#" + m;
for(int i=1; i<(int)n.size(); i++) {
int j = pi[i-1];
while(j > 0 and n[i] != n[j]) j = pi[j-1];
if(n[i] == n[j]) j++;
pi[i] = j;
}
int nr = 0;
vector<int> ans;
for(int i=temp; i<(int)n.size(); i++)
if(pi[i] == temp - 1) {
nr++;
if(ans.size() < 1000) ans.emplace_back(i - 2 * temp + 2);
}
g << nr << "\n";
for(auto i : ans) g << i << " ";
return 0;
}