Pagini recente » Cod sursa (job #1024981) | Cod sursa (job #3248241) | Cod sursa (job #2540621) | Cod sursa (job #2705646) | Cod sursa (job #2979686)
#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;
}