Pagini recente » Cod sursa (job #1665427) | Cod sursa (job #2118873) | Cod sursa (job #580163) | Cod sursa (job #2676806) | Cod sursa (job #2979731)
#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;
}
vector<int> ans;
for(int i=temp; i<(int)n.size(); i++)
if(pi[i] >= temp - 1)
ans.emplace_back(i - 2 * temp + 2);
g << ans.size() << "\n";
for(auto i : ans) g << i << " ";
return 0;
}