Pagini recente » Cod sursa (job #2020619) | Cod sursa (job #1852812) | Cod sursa (job #1625254) | Cod sursa (job #2981418) | Cod sursa (job #2301617)
#include <fstream>
#include <string>
#include <vector>
#define N 1000000
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int main() {
string A, B; cin >> A >> B;
int z[N + 1];
z[0] = 0;
int st = 0, dr = 0;
for(int i = 1; i < A.size(); i++){
if (i > dr){
z[i] = 0;
while(i + z[i] < A.size() && A[i + z[i]] == A[z[i]])
z[i]++;
st = i;
dr = i + z[i] - 1;
}
else {
z[i] = min(z[i - st], dr - i + 1);
if (i + z[i] - 1 == dr){
while(i + z[i] < A.size() && A[i + z[i]] == A[z[i]])
z[i]++;
st = i;
dr = i + z[i] - 1;
}
}
}
st = dr = -1;
int dp[N + 1];
vector<int> ans;
for(int i = 0; i < B.size(); i++){
if (i > dr){
dp[i] = 0;
while(i + dp[i] < B.size() && dp[i] < A.size() && B[i + dp[i]] == A[dp[i]])
dp[i]++;
st = i;
dr = i + dp[i] - 1;
}
else {
dp[i] = min(dp[i - st], dr - i + 1);
if (i + dp[i] - 1 == dr){
while(i + dp[i] < B.size() && dp[i] < A.size() && B[i + dp[i]] == A[dp[i]])
dp[i]++;
st = i;
dr = i + dp[i] - 1;
}
}
if (dp[i] == A.size()) ans.push_back(i);
}
cout << ans.size() << endl;
for(int i = 0; i < ans.size(); i++)
cout << ans[i] << ' ';
return 0;
}