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
#include
#include
using namespace std; typedef long long ll; const int alphabet_size = 26; const int base = 53; const ll MOD = 922337186621; void rolling_hash(string & s, int window_size, string & pattern) { 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; ll res_hash = 0; set
> st; for(int i = 0; i < window_size; i++) { res_hash = (res_hash * alphabet_size + pattern[i]) % MOD; } for(int i = 0; i < window_size; i++) { hash = (hash * alphabet_size + s[i]) % MOD; } int res =0 ; if(hash == res_hash) { bool ok = true; for(int j = 0; j < window_size; j++) { if(pattern[j] != s[j]) { ok = false; break; } } if(ok) { cout << 0 << endl; } } 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; } } } } int main() { ios_base::sync_with_stdio(false); int win_size; string text, pattern; while(cin >> win_size >> pattern >> text) { rolling_hash(text, win_size, 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)