http://www.bnuoj.com/bnuoj/problem_show.php?pid=4352
【题意】:给你个长串,输出该长串中能第一放出的技能,每个技能有对应的一个小子串,不能放出任何技能输出“Nothing Happened”
【题解】:暴力匹配(数据量不大),若数据量巨大,则得用ac自动机解
【code】:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm> using namespace std;
#define INF 1e9 struct Nod
{
char str1[];
char str2[];
}node[]; int findPos(char *str,int len,int p)
{
int i,j;
int len1 = strlen(node[p].str1);
for(i=,j=;i<len;i++)
{
while(node[p].str1[j]==str[i])
{
j++;
i++;
if(j==len1) return i-j;
if(i>=len) break;
}
i=i-j;
j=;
}
return INF;
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
char names[];
scanf("%s",names);
int n;
scanf("%d",&n);
int i;
for(i=;i<n;i++)
{
scanf("%s %s",node[i].str1,node[i].str2);
}
char str[];
scanf("%s",str);
int len = strlen(str);
int minPos=INF,pos;
for(i=;i<n;i++)
{
int temp = findPos(str,len,i);
if(minPos>temp)
{
minPos=temp;
pos = i;
}
}
puts(names);
if(minPos==INF)
{
puts("Nothing Happened");
}
else
{
puts(node[pos].str2);
}
putchar();
}
return ;
}