Pagini recente » Cod sursa (job #3359163) | Monitorul de evaluare | Cod sursa (job #3359169) | Cod sursa (job #3359160) | Cod sursa (job #3359156)
#include <fstream>
#pragma GCC optimize("O3,unroll-loops")
#include <algorithm>
#include <cstring>
#include <climits>
#include <iomanip>
#include <numeric>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#define int long long
//#define int short
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int nmax = 4e6;
string a, b;
int n, m;
int pi[nmax + 5];
void fastio(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
}
void handleinput(){
cin>>a>>b;
}
void setup(){
n = a.size();
m = b.size();
a = a + '#' + b;
m += n + 1;
for (int i = 1; i < m; i++){
int j = pi[i - 1];
while (j && a[j] != a[i]){
j = pi[j - 1];
}
if (a[j] == a[i]){
j++;
}
pi[i] = j;
}
}
void handleoutput(){
int rez = 0;
for (int i = 1; i < m; i++){
rez += (pi[i] == n) ? 1 : 0;
}
cout<<rez<<"\n";
int cnt = 0;
for (int i = 1; i < m; i++){
if (pi[i] == n){
cout<<i - 2 * n<<" ";
cnt++;
}
if (cnt == 1000){
break;
}
}
}
signed main(){
fastio();
handleinput();
setup();
handleoutput();
}