bnu 4352 XsugarX的疯狂按键识别(暴力模拟)

http://www.bnuoj.com/bnuoj/problem_show.php?pid=4352

【题意】：给你个长串，输出该长串中能第一放出的技能，每个技能有对应的一个小子串，不能放出任何技能输出“Nothing Happened”

【题解】：暴力匹配（数据量不大），若数据量巨大，则得用ac自动机解

【code】：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 #define INF 1e9
 8 
 9 struct Nod
10 {
11     char str1[40];
12     char str2[40];
13 }node[20];
14 
15 int findPos(char *str,int len,int p)
16 {
17     int i,j;
18     int len1 = strlen(node[p].str1);
19     for(i=0,j=0;i<len;i++)
20     {
21         while(node[p].str1[j]==str[i])
22         {
23             j++;
24             i++;
25             if(j==len1) return i-j;
26             if(i>=len)  break;
27         }
28         i=i-j;
29         j=0;
30     }
31     return INF;
32 }
33 
34 int main()
35 {
36     int t;
37     scanf("%d",&t);
38     while(t--)
39     {
40         char names[50];
41         scanf("%s",names);
42         int n;
43         scanf("%d",&n);
44         int i;
45         for(i=0;i<n;i++)
46         {
47             scanf("%s %s",node[i].str1,node[i].str2);
48         }
49         char str[100];
50         scanf("%s",str);
51         int len = strlen(str);
52         int minPos=INF,pos;
53         for(i=0;i<n;i++)
54         {
55             int temp = findPos(str,len,i);
56             if(minPos>temp)
57             {
58                 minPos=temp;
59                 pos = i;
60             }
61         }
62         puts(names);
63         if(minPos==INF)
64         {
65             puts("Nothing Happened");
66         }
67         else
68         {
69             puts(node[pos].str2);
70         }
71         putchar(10);
72     }
73     return 0;
74 }