1 /*  2 Source Code  3   4 Problem: 1200        User: robinho364  5 Memory: 40504K        Time: 63MS  6 Language: G++        Result: Accepted  7 */  8 #define _USE_MATH_DEFINES  9  10 #ifdef ONLINE_JUDGE 11 #define FINPUT(file) 0 12 #define FOUTPUT(file) 0 13 #else 14 #define FINPUT(file) freopen(file,"r",stdin) 15 #define FOUTPUT(file) freopen(file,"w",stdout) 16 #endif 17  18 #include <iostream> 19 #include <cstdio> 20 #include <cstring> 21 #include <cstdlib> 22 #include <cmath> 23 #include <ctime> 24 #include <set> 25 #include <stack> 26 #include <string> 27 #include <map> 28 #include <vector> 29 #include <queue> 30 #include <algorithm> 31 #include <functional> 32  33 typedef long long ll; 34 static const int N = 16000010; 35 static const int M = 20; 36 static const int LEN = 100; 37 static const int MAX = 0x7fffffff; 38 static const int GMAX = 0x3f3f3f3f; 39 static const int MIN = ~MAX; 40 static const double EPS = 1e-7; 41 static const int BASE = 10000007; 42 static const int CH = 27; 43 char str[N]; 44 int hash[BASE]; 45 int char_to_num[257]; 46  47 bool inline cmp(int i, int j, int n) 48 { 49     int res = strncmp(str + i, str + j, n); 50     if (res) { 51         return false; 52     } else { 53         return true; 54     } 55 } 56  57 void inline rabin_karp(int n, int nc, int len) 58 { 59     int seed = 0; 60     for(int i = 0;i<len;i++){ 61         if(char_to_num[str[i]] == 0){ 62             char_to_num[str[i]] = ++seed; 63         } 64     } 65  66     int t = 1; 67  68     for(int i = 0;i<n;i++) 69         t*=nc; 70  71     int ah = 0; 72  73     for(int i = 0;i<n;i++) 74         ah = (ah*nc + char_to_num[str[i]]) % BASE; 75  76     int ncount = 0; 77     for(int i = 0;i+n<=len;i++){ 78         if(!hash[ah]){ 79             hash[ah] = i + 1; 80             ncount++; 81         } else { 82             int res = ah; 83             while (hash[res] && !cmp(i, hash[res] - 1, n)) { 84                 res = (res + 1) % BASE; 85             } 86             hash[res] = i + 1; 87         } 88         if(i+n<len){ 89             ah = (ah*nc + char_to_num[str[i+n]] - char_to_num[str[i]]*t)%BASE; 90         } 91     } 92  93     printf("%d\n", ncount); 94 } 95  96 int main() 97 { 98     FINPUT("in.txt"); 99     FOUTPUT("out.txt");100 101     int n, nc;102     while (scanf("%d %d", &n, &nc) != EOF) {103         scanf("%s", str);104         memset(char_to_num, 0, sizeof(char_to_num));105         memset(hash, false, sizeof(hash));106         rabin_karp(n, nc + 1, strlen(str));107     }108 109     return 0;110 }

 1 /* 2 Source Code 3  4 Problem: 1200        User: robinho364 5 Memory: 17008K        Time: 32MS 6 Language: G++        Result: Accepted 7 */ 8 #define _USE_MATH_DEFINES 9 10 #ifdef ONLINE_JUDGE11 #define FINPUT(file) 012 #define FOUTPUT(file) 013 #else14 #define FINPUT(file) freopen(file,"r",stdin)15 #define FOUTPUT(file) freopen(file,"w",stdout)16 #endif17 18 #include <iostream>19 #include <cstdio>20 #include <cstring>21 #include <cstdlib>22 #include <cmath>23 #include <ctime>24 #include <set>25 #include <stack>26 #include <string>27 #include <map>28 #include <vector>29 #include <queue>30 #include <algorithm>31 #include <functional>32 33 typedef long long ll;34 static const int N = 16000010;35 static const int M = 20;36 static const int LEN = 100;37 static const int MAX = 0x7fffffff;38 static const int GMAX = 0x3f3f3f3f;39 static const int MIN = ~MAX;40 static const double EPS = 1e-7;41 static const int BASE = 6000011;42 static const int CH = 27;43 char str[N];44 bool hash[N];45 int char_to_num[257];46 47 void inline rabin_karp(int n, int nc, int len)48 {49     int seed = 0;50     for(int i = 0;i<len;i++){51         if(char_to_num[str[i]] == 0){52             char_to_num[str[i]] = ++seed;53         }54     }55 56     int t = 1;57 58     for(int i = 0;i<n;i++)59         t*=nc;60 61     int ah = 0;62 63     for(int i = 0;i<n;i++)64         ah = ah*nc + char_to_num[str[i]];65 66     int ncount = 0;67     for(int i = 0;i+n<=len;i++){68         if(hash[ah] == false){69             hash[ah] = true;70             ncount++;71         }72         if(i+n<len){73             ah = ah*nc + char_to_num[str[i+n]] - char_to_num[str[i]]*t;74         }75     }76 77     printf("%d\n", ncount);78 }79 80 int main()81 {82     FINPUT("in.txt");83     FOUTPUT("out.txt");84 85     int n, nc;86     while (scanf("%d %d", &n, &nc) != EOF) {87         scanf("%s", str);88         memset(char_to_num, 0, sizeof(char_to_num));89         memset(hash, false, sizeof(hash));90         rabin_karp(n, nc + 1, strlen(str));91     }92 93     return 0;94 }