Pagini recente » Cod sursa (job #2886679) | Cod sursa (job #1484051) | Cod sursa (job #766821) | Cod sursa (job #2447437) | Cod sursa (job #3147245)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
//#define int long long
const string FILE_NAME = "strmatch";
ifstream fin(FILE_NAME + ".in");
ofstream fout(FILE_NAME + ".out");
vector<int> lps(string s){
vector<int> v_lps(s.size(), 0);
int len = 0;
for(int i = 1; i < s.size();){
if(s[i] == s[len]){
len++;
v_lps[i] = len;
i++;
}
else{
if(len != 0){
len = v_lps[len - 1];
}
else
v_lps[i] = 0, i++;
}
}
return v_lps;
}
signed main()
{
string a,b;
fin >> a >> b;
int n = 0;
vector <int> v_lps = lps(a);
vector <int> answer;
for(int i = 0, j = 0; i < b.size();){
if(b[i] == a[j]){
i++; j++;
if(j == a.size()){
n++;
if(answer.size() < 1000)
answer.pb(i - j);
j = v_lps[j - 1];
}
}
else{
if(j != 0){
j = v_lps[j - 1];
}
else
i++;
}
}
fout << n << "\n";
for(int i = 0; i < answer.size(); i++)
fout << answer[i] << " ";
return 0;
}