Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- ll mod = 1000000007;
- #define max 100005
- int p = 31;
- ll hashfunction[max], power[max];
- void precompute(string text, int n){
- power[0]=1;
- hashfunction[0] = text[0]-'a'+1;
- ll pow = p;
- for(int i=1; i<n; i++){
- power[i] = pow;
- hashfunction[i] = (hashfunction[i-1] + ((text[i]-'a'+1)*pow)%mod)%mod;
- pow = (pow * p)%mod;
- }
- }
- ll getHash(int l, int r){
- if(l==0) return hashfunction[r];
- else return (mod + hashfunction[r] - (hashfunction[l-1]*power[r-l+1])%mod)%mod;
- }
- ll computeHashofstring(string pattern){
- ll hash_value = 0;
- for(int i=0; i<pattern.length(); i++){
- hash_value += ((pattern[i]-'a'+1)*power[i])%mod;
- }
- return hash_value;
- }
- vector<int> solve(string text, string pattern){
- vector<int> v;
- precompute(text, text.length());
- ll hashofpattern = computeHashofstring(pattern);
- int left=0, right=pattern.length()-1;
- while (right<text.length())
- {
- if(hashofpattern == getHash(left,right)){
- v.push_back(left);
- }
- left++,right++;
- }
- return v;
- }
- int main(){
- string text, pattern;
- cin >> text >> pattern;
- vector<int> v = solve(text, pattern);
- for(int i=0; i<v.size(); i++) cout << v[i] << '\n';
- return 0;
- }
Add Comment
Please, Sign In to add comment