結果
| 問題 | No.430 文字列検索 |
| ユーザー |
 夜
|
| 提出日時 | 2021-03-02 19:50:31 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 1,380 bytes |
| コンパイル時間 | 1,852 ms |
| コンパイル使用メモリ | 98,404 KB |
| 実行使用メモリ | 817,664 KB |
| 最終ジャッジ日時 | 2024-11-10 00:53:19 |
| 合計ジャッジ時間 | 2,940 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 6 ms
9,728 KB |
| testcase_01 | MLE | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
ソースコード
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
int suf[200020], r[200020], r_mem[200020];
int n;
string suf1[200020];
string s;
int k;
bool suf_sort(int i, int j) {
int i1, i2, j1, j2;
i1 = r[i];
if (i + k > n)i2 = -1;
else i2 = r[i + k];
j1 = r[j];
if (j + k > n)j2 = -1;
else j2 = r[j + k];
if (make_pair(i1, i2) < make_pair(j1, j2))return true;
else return false;
}
void c_suf(){
for (int i = 0; i <= n; i++) {
suf[i] = i;
if (i == n)r[i] = -1;
else r[i] = s[i] - 'A';
}
for (k = 1; k <= n; k *= 2) {
sort(suf, suf + n + 1, suf_sort);
r_mem[suf[0]] = 0;
for (int j = 1; j <= n; j++) {
r_mem[suf[j]] = r_mem[suf[j - 1]];
if (suf_sort(suf[j - 1], suf[j]))r_mem[suf[j]]++;
}
for (int j = 0; j <= n; j++) {
r[j] = r_mem[j];
}
}
}
int main(){
cin >> s;
n = s.size();
c_suf();
for (int i = 0; i <= n; i++) {
suf1[i] = s.substr(suf[i], n - suf[i]);
}
int m;
cin >> m;
int ans = 0;
for (int i = 0; i < m; i++) {
string c;
cin >> c;
auto itr = lower_bound(suf1, suf1 + n + 1, c);
auto itr1 = lower_bound(suf1, suf1 + n + 1, c + '{');
ans += int(itr1 - itr);
}
cout << ans << endl;
}