首页 > ACM题库 > HDU-杭电 > HDU 2752-HOJ-WiFi-KMP-[解题报告]C++
2014
02-14

HDU 2752-HOJ-WiFi-KMP-[解题报告]C++

WiFi

问题描述 :

One day, the residents of Main Street got together and decided that they would install wireless internet on their street, with coverage for every house. Now they need your help to decide where they should place the wireless access points. They would like to have as strong a signal as possible in every house, but they have only a limited budget for purchasing access points. They would like to place the available access points so that the maximum distance between any house and the access point closest to it is as small as possible.

Main Street is a perfectly straight road. The street number of each house is the number of metres from the end of the street to the house. For example, the house at address 123 Main Street is exactly 123 metres from the end of the street.

输入:

The first line of each test chunk contains an integer specifying the number of test cases in this chunk to follow. The first line of each test case contains two positive integers n, the number of access points that the residents can buy, and m, the number of houses on Main Street. The following m lines contain the house numbers of the houses on Main Street, one house number on each line. There will be no more than 100 000 houses on Main Street, and the house numbers will be no larger than one million.
Please process to the end of the data file.

输出:

The first line of each test chunk contains an integer specifying the number of test cases in this chunk to follow. The first line of each test case contains two positive integers n, the number of access points that the residents can buy, and m, the number of houses on Main Street. The following m lines contain the house numbers of the houses on Main Street, one house number on each line. There will be no more than 100 000 houses on Main Street, and the house numbers will be no larger than one million.
Please process to the end of the data file.

样例输入:

1
2 3
1
3
10
1
2 3
1
3
10

样例输出:

1.0
1.0

题意:给出字符串,求所有既是前缀又是后缀的串的大小。

思路:KMP的next[]应用。。
例如题目给出的串  ababcababababcabab
对应的next值  -1,0,0,1,2,0,1,2,3,4,3,4,3,4,5,6,7,8,9(next[18])
next[18]=9,代表着位置18以前的既是前缀,又是后缀的串最大是9(不包括本身),然后找
next[9]=4,也就是位置9以前,有4个是前缀,并且和位置9向前数4个的字符串相同,因为位置9以前的字符串(9个)和位置18以前的9个字符串(也就是末尾的9个)相同,所以next[9]=4也代表了有4个字符串既是前缀也是后缀。同理,next[4]=2.  next[2]=0,不再找了。。如果首字母等于尾字母,那么也算一个前后缀,数值等于1.
开一个数组tmp,把2,4,9,18(本身字符串大小,可以看作是最大的前后缀)存起来,然后循环输出即可。。
#include<iostream>
using namespace std;
int next[400005];
char s[400005];
int len;
void get_next()
{
  int k=-1,j=0;
  next[0]=-1;
  len=strlen(s);
  while(j<len)
  {
    if(k==-1||s[j]==s[k])
    {
      next[j+1]=k+1;
      j++;k++;
    }
    else
    k=next[k];
  }
}
int main()
{
  int tmp[400005];
  while(scanf("%s",s)!=EOF)
  {
    int i=1;
    get_next();
    for(int g=0;g<=len;g++)
    printf("%d ",next[g]);
    int end=len;
    tmp[0]=len;
    while(next[len]!=0)//递归的找
    {
      tmp[i++]=next[len];
      len=next[len];
    }
    if(s[0]==s[end])
    printf("1 ");
    for(int j=i-1;j>0;j--)
    printf("%d ",tmp[j]);
    printf("%d\n",tmp[0]);
  }
}

解题参考:http://blog.csdn.net/a402630999/article/details/7208235


,
  1. 我还认为美狗得了狂犬病死了,或被打狗队收容了,怎么又跳出来了?无产阶级夺取政权后,象你这样的被打倒的牛鬼蛇神及其狗崽子、反动派的残渣余孽必然垂死挣扎,以百倍的疯狂进行捣乱和破坏。而且新生的资产阶级和蜕化变质分子以各种手段夺取政权,不进行无产阶级专政均阶级

  2. 慢着,你这有可能不是讽刺?!就因为举例的刚好是代码梗DSB941?所以你有可能弱智到不去理解叙述的事情本身,而因为举的例是DSB,就先入为主认为我会认定NSFW也是代码梗?晕,妹子图未划出来前,就一大波人拿NSFW说事才划出个妹子图,我是不敢想象在煎蛋还

  3. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  4. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢