Pagini recente » Cod sursa (job #993883) | Cod sursa (job #82445) | Cod sursa (job #153345) | Cod sursa (job #2238757) | Cod sursa (job #1856154)
#include <bits/stdc++.h>
using namespace std;
char str[(int)4e6 + 10];
int pi[sizeof(str)], *match;
void build_pi(char *str, const int n){
for(int i = 1, k = 0; i < n; ++i){
while(str[k] != str[i] && k) k = pi[k-1];
if(str[k] == str[i]) ++k;
pi[i] = k; } }
int main(){
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f >> str;
const int n = strlen(str);
f >> (str+n+1);
const int m = strlen(str+n+1);
str[n] = '#';
build_pi(str, n+m+1);
int rez = 0;
vector<int> pozs;
for(int i = 0; i < m; ++i){
if(pi[n+i+1] == n){
++rez;
if(pozs.size() < 1000) pozs.push_back(i+1 - n); } }
g << rez << '\n';
for(const auto x : pozs){
g << x << ' '; }
return 0; }