Pagini recente » Cod sursa (job #2280898) | Cod sursa (job #954482) | Cod sursa (job #2056879) | Cod sursa (job #1668843) | Cod sursa (job #3146618)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define tie_ion_base cin.tie(NULL);ios_base::sync_with_stdio(false);
#define int long long
#define cin fin
#define cout fout
const string FILE_NAME = "strmatch";
ifstream fin(FILE_NAME + ".in");
ofstream fout(FILE_NAME + ".out");
vector<int> lps(string a){
vector <int> v(a.size(), 0);
int len = 0;
for(int i = 1; i < a.size();){
if(a[i] == a[len]){
len++;
v[i] = len;
i++;
}
else{
if(len != 0){
len = v[len - 1];
}
else
v[i] = 0, i++;
}
}
return v;
}
signed main()
{
tie_ion_base;
string a, b;
int p = 0, n = 0;
cin >> a >> b;
vector <int> v = lps(a);
vector <int> array;
for(int i = 0, j = 0; i < b.size();){
if(b[i] == a[j]){
j++;
i++;
if(j == a.size()){
n++;
if(n <= 1000)
array.pb(i - j);
j = v[j - 1];
}
}
else{
if(j != 0)
j = v[j - 1];
else
i++;
}
}
cout << n << "\n";
for(int i = 0; i < n && i < 1000; i++){
cout << array[i] << " ";
}
return 0;
}