Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
#include
using namespace std; typedef long long ll; const int alphabet_size = 26; const ll MOD = 1e9 + 7; void rolling_hash(string s, int window_size, string pattern) { ll res_hash = 0; for(int i = 0; i < (int) pattern.size(); i++) { res_hash = (res_hash * alphabet_size + pattern[i]) % MOD; } int n = (int) s.size(); vector
powers(n + 1, 1); for(int i = 1; i <= n; i++) { powers[i] = (powers[i - 1] * alphabet_size) % MOD; } ll hash = 0; for(int i = 0; i < window_size; i++) { hash = (hash * alphabet_size + s[i]) % MOD; } if(hash == res_hash) { bool ok = true; for(int i = 0; i < window_size; i++) { if(pattern[i] != s[i]) { ok = false; break; } } if(ok) { cout << 0 << endl; } } vector
res(n - window_size + 1); res[0] = hash; for(int i = 1; i <= n - window_size; i++) { hash = (hash - powers[window_size - 1] * s[i - 1]); while (hash < 0) { hash += MOD; } hash %= MOD; hash = (hash * alphabet_size + s[i + window_size - 1]) % MOD; if(hash == res_hash) { bool ok =true; for(int j = 0; j < window_size; j++) { if(pattern[j] != s[i + j]) { ok = false; break; } } if(ok) { cout << i << endl; } } res[i] = hash; } } int main() { ios_base::sync_with_stdio(false); string text = "AABAACBAA"; string pattern = "BAA"; rolling_hash(text, 3, pattern); return 0; }
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)