結果
問題 | No.430 文字列検索 |
ユーザー |
![]() |
提出日時 | 2020-02-20 02:40:29 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 175 ms / 2,000 ms |
コード長 | 1,750 bytes |
コンパイル時間 | 1,090 ms |
コンパイル使用メモリ | 160,228 KB |
実行使用メモリ | 7,424 KB |
最終ジャッジ日時 | 2024-11-10 00:41:03 |
合計ジャッジ時間 | 3,400 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define ll long long int#define rep(i,n) for( int i = 0; i < n; i++ )#define rrep(i,n) for( int i = n; i >= 0; i-- )#define REP(i,s,t) for( int i = s; i <= t; i++ )#define RREP(i,s,t) for( int i = s; i >= t; i-- )#define dump(x) cerr << #x << " = " << (x) << endl;#define INF 2000000000#define mod 92709568269121#define INF2 1000000000000000000#define int long longint H(string s) {int num = 0;rep(i, s.size()) {num = (num * 26) % mod;num = (num + (s[i] - 'A' + 1)) % mod;}return num;}int Mul(int a, int b) {return ((a % mod) * (b % mod)) % mod;}int square(int x) {return (x * x) % mod;}int power(int x, int y) {if (y == 0) return 1;else if (y == 1) return x % mod;else if (y % 2 == 0) return square(power(x, y / 2)) % mod;else return square(power(x, y / 2)) * x % mod;}int H2[11][50010];signed main(void){cin.tie(0);ios::sync_with_stdio(false);string S; cin >> S;int M; cin >> M;int ans = 0;REP(k, 1, 10) {int num1 = 0;int cnt = 0;rep(i, S.length()) {num1 = (num1 * 26) % mod;num1 = (num1 + (S[i] - 'A' + 1)) % mod;cnt++;//cout << num << " " << num1 << " ";H2[k][i] = num1;if (cnt == k) {num1 = (num1 - power(26, cnt - 1) * (S[i - cnt + 1] - 'A' + 1) + mod) % mod;cnt--;}//cout << ans << endl;}}while(M--) {string s; cin >> s;int num = H(s);int cnt = 0;int num1 = 0;rep(i, S.length()) if (H2[s.length()][i] == num) ans++;}cout << ans << endl;return 0;}