結果
問題 | No.430 文字列検索 |
ユーザー |
|
提出日時 | 2016-10-02 23:39:46 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 111 ms / 2,000 ms |
コード長 | 1,597 bytes |
コンパイル時間 | 1,200 ms |
コンパイル使用メモリ | 68,112 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-10 00:04:26 |
合計ジャッジ時間 | 1,882 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 |
ソースコード
#include<iostream> #include<algorithm> #include<vector> #include<cstring> using namespace std; const int BUF = 50005; const int WORD = 5005; class Sorter{ public: int *v, h; Sorter(){} Sorter(int *v, int h): v(v), h(h){} bool operator()(int a, int b){ if(a==b) return false; if(v[a]!=v[b]) return v[a]<v[b]; return v[a+h]<v[b+h]; } }; vector<char*> construct(char *txt){ int N = strlen(txt); static int V[BUF], pos[BUF], buf[BUF]; txt[N++] = '\0'; for(int i=0;i<N;i++){ pos[i] = i; V[i] = txt[i]; } sort(pos,pos+N,Sorter(V,0)); for(int h=1;h<N;h<<=1){ Sorter sorter(V,h); sort(pos,pos+N,sorter); buf[0] = 0; for(int i=1;i<N;i++) buf[i] = buf[i-1] + !(V[pos[i-1]]==V[pos[i]] && V[pos[i-1]+h]==V[pos[i]+h]); for(int i=0;i<N;i++) V[pos[i]] = buf[i]; } vector<char*> ret; for(int i=0;i<N;i++) ret.push_back(txt+pos[i]); return ret; } char txt[BUF]; int nWord; string word[WORD]; void read() { cin >> txt; cin >> nWord; for (int i = 0; i < nWord; ++i) { cin >> word[i]; } } void work() { vector<char*> sarray = construct(txt); int cnt = 0; for (int i = 0; i < nWord; ++i) { vector<char*>::iterator bgn = lower_bound(sarray.begin(), sarray.end(), word[i]); ++word[i][word[i].size() - 1]; vector<char*>::iterator end = lower_bound(sarray.begin(), sarray.end(), word[i]); cnt += end - bgn; } cout << cnt << endl; } int main() { read(); work(); return 0; }