ACM_名字的价值

名字的价值

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

集训终于开始了，参加集训的人很多，也就有很多名字，集训组织者发现了一件很神奇的事情，竟然可以用一个神奇的字符串表示所有人的名字。该字符串的所有子串都对应着一个人的名字。然后他给一些名字设定了一个价值（没有设定到的,价值为0）。现在求所有人名字的价值和。

字符串的子串指的是如ABC的子串有A,B,C,AB,BC,ABC。

Input:

输入包含多组数据，对于每组数据首先是一个整数n（1<=n<=1000）,接下来n行输入一个名字si(1<=length<=100)和一个价值vi(0=<vi<=100)。保证输入的所有名字不同，并且只包含字母，区分大小写。

接下来是输入一个神奇的字符串s(1<=length<=100)。

Output:

对于每组数据，输出所有人名字的价值和。

Sample Input:

3

A 3

B 5

ABC 7

ABC

2

AA 2

B 2

AAAB

Sample Output:

15

6
解题思路：题目的意思就是计算所有子串的价值总和，其中子串必须是由连续字符组成的。做法：从下标0位置开始查找是否含有每个子串，如果有（string.find(string,pos(size_t类型))返回的是第一次出现的位置）就将pos加1后继续查找，只要不返回string::npos，都将其价值累加，水过！
AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 string rst,obj[maxn];int val[maxn];

 size_t pos,n,sum;

 int main(){

     while(~scanf("%d",&n)){getchar();//吃掉回车符对字符串的影响

         for(size_t i=;i<n;++i)cin>>obj[i]>>val[i];

         cin>>rst;sum=;

         for(size_t i=;i<n;++i){pos=;//从下标0开始查找

             while((pos=rst.find(obj[i],pos))!=string::npos){sum+=val[i];pos+=;}

         }

         printf("%d\n",sum);

     }

     return ;

 }