Try   HackMD

【CSES】1753. String Matching

題目連結

時間複雜度

  • O(N)

解題想法

首先,這一題最樸素的做法不難得出是

O(N2) ,但是很顯然的這個超過 1e6 的測資這個時間複雜度是 100% 不會過的

因此這題要使用的就是字串哈希 String Hash 這一個解法,字串哈希簡單來說就是將一段字串壓縮成一個數字,透過比對數字就可以快速地得出兩個字串是否可能相同

所以這題的完整解法就是先建一個模板的哈希表,接著再在算出要比對的那個字串的哈希值,最後用

O(N) 直接掃到底就可以了

完整程式

/* Question : CSES 1753. String Matching */ #include<bits/stdc++.h> using namespace std; #define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define pirq(type) priority_queue<type, vector<type>, greater<type>> #define mem(x, value) memset(x, value, sizeof(x)); #define pii pair<int, int> #define pdd pair<double, double> #define pb push_back #define f first #define s second #define int long long const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} }; const int MAXN = 1e8 + 50; const int Mod = 1e9 + 7; const int p = 48763, q = 1e9 + 7; vector<int> hstr, hc, ksm; string str, cmp; int amt, vs; void hsh(){ int len = str.size(); hstr.resize(len); ksm.resize(len); hstr[0] = str[0]; ksm[0] = 1; for( int i = 1 ; i < len ; i++ ){ hstr[i] = ( ( hstr[i-1] * p ) % q + str[i] ) % q; ksm[i] = ( ksm[i-1] * p ) % q; } return; } int get( int l, int r ){ if( l == 0 ) return hstr[r]; int res = ( hstr[r] - ( hstr[l - 1] * ksm[r-l+1] ) % q ) % q; if( res < 0 ) res += q; return res; } signed main(){ // opt; cin >> str >> cmp; // Get Hash Value /* str */ hsh(); /* cmp */ vs = cmp[0]; for( int i = 1 ; i < cmp.size() ; i++ ) vs = ( ( vs * p ) % q + cmp[i] ) % q; if( str.size() >= cmp.size() ){ for( int i = 0 ; i < str.size() - ( cmp.size() - 1 ) ; i++ ){ if( get( i, i + ( cmp.size() - 1 ) ) == vs ) amt++; } } cout << amt << "\n"; }