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

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