Pagini recente » Cod sursa (job #762888) | Cod sursa (job #526315) | Cod sursa (job #2918594) | Cod sursa (job #88479) | Cod sursa (job #2408427)
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
const string file = "strmatch";
const ll INF = 9223372036854775807ll;
const int inf = 2147483647, nmax = 2000006;
string v, r;
int pred[nmax];
int main()
{
ifstream fin (file+".in");
ofstream fout (file+".out");
fin >> v >> r; v += "#";
pred[0] = -1;
for (int i = 1; i < v.length()-1; ++i){
int now = pred[i-1];
while(now != -1 && v[now+1] != v[i])
now = pred[now];
if(v[now+1] == v[i])
++now;
pred[i] = now;
}
int now = -1, sol = 0;;
vector<int> ans;
for (int i = 0; i < r.length(); ++i){
while(now != -1 && v[now+1] != r[i])
now = pred[now];
if(v[now+1] == r[i])
++now;
if(now == v.length()-2){
++sol;
if(sol <= 1000)
ans.push_back(i-now);
}
}
fout << sol << "\n";
for (auto x : ans)
fout << x << " ";
return 0;
}