Pagini recente » Cod sursa (job #157816) | Cod sursa (job #1362279) | Cod sursa (job #1407540) | Cod sursa (job #169095) | Cod sursa (job #3169056)
#include <deque>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iostream>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#define pb push_back
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
typedef long long ll;
typedef pair<int, int> pi;
int t, T;
void KMP() {
string P, T;
f >> P >> T;
P = " " + P;
T = " " + T;
int n = P.size();
vector<int> dpP(n, 0);
for (int i = 2; i < n; i++) {
int K = dpP[i - 1];
while (K > 0 && P[i] != P[K + 1]) K = dpP[K];
dpP[i] = K + (P[i] == P[K + 1]);
}
int m = T.size();
vector<int> dpT(m, 0);
int ans = 0;
vector<int> poz;
for (int i = 1; i < m; i++) {
int K = dpT[i - 1];
while (K > 0 && T[i] != P[K + 1]) K = dpP[K];
dpT[i] = K + (T[i] == P[K + 1]);
if (dpT[i] == n - 1) {
ans++;
if (ans <= 1000) {
poz.push_back(i - n + 1);
}
}
}
g << ans << '\n';
for (int x : poz) g << x << ' ';
}
void Z() {
string P, T;
f >> P >> T;
string S = P + T;
int n = S.size();
vector<int> dp(n, 0);
int ans = 0;
vector<int> poz;
int l = 0, r = 0;
dp[0] = 1;
for (int i = 1; i < n; i++) {
int j = min(dp[i - l], r - i + 1);
while (i + j < n && S[i + j] == S[j]) j++;
dp[i] = j;
if (i + j > r) {
l = i;
r = i + j;
}
if (dp[i] == P.size()) {
ans++;
if (ans <= 1000) {
poz.push_back(i - P.size());
}
}
}
g << ans << '\n';
for (int x : poz) g << x << ' ';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
Z();
return 0;
}