# 【CSES】1753. String Matching

## [題目連結](https://cses.fi/problemset/task/1753)

## **時間複雜度**

* $O(N)$

## **解題想法**

首先，這一題最樸素的做法不難得出是 $O(N^2)$ ，但是很顯然的這個超過 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";
}