?

之前做過(guò)的oj， acm題目忘了很多了， 又要開(kāi)始要刷題了， go on!

?

?

#1260 : String Problem I

時(shí)間限制:10000ms 單點(diǎn)時(shí)限:1000ms 內(nèi)存限制:256MB

描述

我們有一個(gè)字符串集合S，其中有N個(gè)兩兩不同的字符串。

還有M個(gè)詢問(wèn)，每個(gè)詢問(wèn)給出一個(gè)字符串w，求有多少S中的字符串可以由w添加恰好一個(gè)字母得到。

字母可以添加在包括開(kāi)頭結(jié)尾在內(nèi)的任意位置，比如在"abc"中添加"x"，就可能得到"xabc", "axbc", "abxc", "abcx".這4種串。

輸入

第一行兩個(gè)數(shù)N和M，表示集合S中字符串的數(shù)量和詢問(wèn)的數(shù)量。

接下來(lái)N行，其中第i行給出S中第i個(gè)字符串。

接下來(lái)M行，其中第i行給出第i個(gè)詢問(wèn)串。

所有字符串只由小寫字母構(gòu)成。

數(shù)據(jù)范圍：

N,M<=10000。

S中字符串長(zhǎng)度和<=100000。

所有詢問(wèn)中字符串長(zhǎng)度和<=100000。

輸出

對(duì)每個(gè)詢問(wèn)輸出一個(gè)數(shù)表示答案。

樣例輸入

3 3 tourist petr rng toosimple rg ptr

樣例輸出

0 1 1

?

?

二分查找，在大型數(shù)組中很常用。

?

?

#include <cstdio> #include <iostream> #include <cstring> #include <cstdlib> #include <string> #include <cmath> using namespace std; const int maxn = 10005; struct Node{int len; string s; }nd[maxn]; int n,m; int Match(const string &s1, const string &s2){bool isPlus = true; int j = 0; for(int i=0; i<s1.length(); i++){if(s1[i] != s2[j]){if(isPlus){isPlus = false; }else{return false; }}else{j++; }}return true; }int cmp(const void* a, const void* b){Node* aa = (Node *)a; Node* bb = (Node *)b; return aa->len - bb->len; }int main(){freopen("in.txt", "r", stdin); int i,j, mid, left, right, target_len, test_start, cnt; string target; scanf("%d %d", &n, &m ); getchar(); for(int i=0; i<n; i++){cin>>nd[i].s;nd[i].len = nd[i].s.length(); }qsort(nd, n, sizeof(nd[0]), cmp); for(i=0; i<m; i++){cin>>target; target_len = target.length() + 1; left = 0; right = n-1; test_start = -1; while(left <= right){mid = left + (right - left)/2; if(nd[mid].len == target_len){j = mid-1; while(j>=0 && nd[j].len == nd[mid].len){j--; }test_start = j + 1; break; }else if(nd[mid].len > target_len){right = mid - 1; }else{left = mid + 1; }}if(test_start == -1){printf("%d\n", 0);}else{cnt = 0; for(j=test_start; nd[j].len == target_len; j++){if(Match(nd[j].s, target)){cnt++; }}printf("%d\n", cnt);}}return 0; }

　　

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhang-yd/p/5774420.html

總結(jié)

以上是生活随笔為你收集整理的hihocoder 1260的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。