Pagini recente » Borderou de evaluare (job #520038) | Cod sursa (job #640665) | Cod sursa (job #2623490) | Cod sursa (job #445187) | Cod sursa (job #2644793)
#include <bits/stdc++.h>
#include <sstream>
using namespace std;
#define ll long long
#define endl "\n"
const int Nmax = 1500;
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
#define cin fin
#define cout fout
/*
ifstream fin("test.in");
#define cin fin
*/
int contor = 0;
int nuStiuSTL[1005];
char a[2000005], b[2000005];
int dp[2000005];
int n, m;
void init() {
dp[1] = 0;
int j = 0;
for(int i = 2; i <= m; i++) {
while(j && a[j + 1] != a[i]) {
j = dp[j];
}
if(a[j + 1] == a[i]) {
j++;
}
dp[i] = j;
}
}
void cautare() {
init();
int j = 0;
for(int i = 1; i <= n; i++) {
while(j && a[j + 1] != b[i]) {
j = dp[j];
}
if(a[j + 1] == b[i]) {
j++;
}
if(j == m) {
j = dp[m];
contor++;
if(contor <= 1000) {
nuStiuSTL[contor] = i - m;
}
}
}
}
void solve() {
a[0] = '.';
b[0] = '.';
cin >> (a + 1) >> (b + 1);
n = strlen(b) - 1;
m = strlen(a) - 1;
cautare();
if(contor > 1000) {
contor = 1000;
}
cout << contor << endl;
for(int i = 1; i <= contor; i++) {
cout << nuStiuSTL[i] << " ";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin .tie(0);
cout.tie(0);
int testCases = 1;
//cin >> testCases;
while(testCases--) {
solve();
}
}