i510 - 尋找子字串
題目描述
題目要求判斷字串 t 是否為字串 s 的子字串，如果是，則輸出 t 在 s 中第一次出現的起始位置（0-indexed）。如果 t 不是 s 的子字串，則輸出 "No"。
解題思路
本題使用 Rolling Hash 演算法來解決子字串匹配問題。Rolling Hash 允許我們在 O(1) 時間內計算字串的雜湊值，並在滑動視窗中快速更新雜湊值。
具體來說，我們首先計算字串 t 的雜湊值。然後，我們遍歷字串 s，計算每個長度等於 t 的子字串的雜湊值。如果子字串的雜湊值等於 t 的雜湊值，我們就檢查該子字串是否真的等於 t（為了避免雜湊衝突）。如果相等，則輸出該子字串的起始位置，並結束程式。如果遍歷完所有子字串後仍然沒有找到匹配的子字串，則輸出 "No"。
為了避免雜湊衝突，我們使用一個大的質數 P 作為 Rolling Hash 的基數，並使用另一個質數 MOD 進行模運算。
複雜度分析
- 時間複雜度: O(n + m)，其中 n 是字串 s 的長度，m 是字串 t 的長度。計算 t 的雜湊值需要 O(m) 時間，遍歷 s 並計算每個子字串的雜湊值需要 O(n) 時間。
- 空間複雜度: O(n)，用於儲存字串 s 的雜湊值。
程式碼
#include <iostream>
#define ll long long
const ll P = 75577,MOD = 998244353;
using namespace std;
ll n,m,Hash[100001],PH[100001]={1},mv;
string x,y;
int main(){
cin.tie(0);cout.tie(0); ios::sync_with_stdio(0);
for(int i=1;i<=100000;++i)
PH[i]=PH[i-1]*P%MOD;
while(cin >> n >> m >> x >> y){
ll mal = 0;
bool ans=0;
for(ll i=0;i<m;++i)
mal = (mal * P + y[i]) % MOD;
for(ll i=1,val=0,mv = PH[m];i<=n;++i){
val = (val * P + x[i-1]) % MOD;
Hash[i] = val;
if(i>=m&&(val-(Hash[i-m]*mv)%MOD+MOD)%MOD==mal){
ans=1;
cout << "Yes\npos: " << i-m << "\n";
break;
}
}
if(ans==0)
cout << "No\n";
}
}