Pagini recente » Cod sursa (job #2671930) | Cod sursa (job #716002) | Cod sursa (job #1030786) | Cod sursa (job #307219) | Cod sursa (job #2848543)
#define boostIO ios_base::sync_with_stdio(false); fin.tie(nullptr); fout.tie(nullptr);
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define uint unsigned int
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int OUT_LIMIT = 1000;
int out_cnt;
queue <int> sol;
const int STR_SIZE = 2000000;
string txt, fnd;
int len, kmp[2 * STR_SIZE + 5];
signed main (){
boostIO
fin>>fnd>>txt;
txt = " " + fnd + "#" + txt;
kmp[0] = -1;
for(int i=1; i < (int)txt.size(); i++){
len = kmp[i-1];
while(len >= 0 && txt[i] != txt[len+1])
len = kmp[len];
kmp[i] = len + 1;
}
for(int i=1; i < (int)txt.size(); i++)
if(kmp[i] == (int)fnd.size())
if(++out_cnt <= OUT_LIMIT)
sol.push(i - 2*(int)fnd.size() - 1);
fout<<out_cnt<<"\n";
while(!sol.empty()){
fout<<sol.front()<<" ";
sol.pop();
}
return 0;
}