首页 > ACM题库 > HDU-杭电 > HDU 1381 Crazy Search-字符串-[解题报告] C++
2013
12-09

HDU 1381 Crazy Search-字符串-[解题报告] C++

Crazy Search

问题描述 :

Many people like to solve hard puzzles some of which may lead them to madness. One such puzzle could be finding a hidden prime number in a given text. Such number could be the number of different substrings of a given size that exist in the text. As you soon will discover, you really need the help of a computer and a good algorithm to solve such a puzzle.

Your task is to write a program that given the size, N, of the substring, the number of different characters that may occur in the text, NC, and the text itself, determines the number of different substrings of size N that appear in the text.

As an example, consider N=3, NC=4 and the text "daababac". The different substrings of size 3 that can be found in this text are: "daa", "aab", "aba", "bab", "bac". Therefore, the answer should be 5.

输入:

The first line of input consists of two numbers, N and NC, separated by exactly one space. This is followed by the text where the search takes place. You may assume that the maximum number of substrings formed by the possible set of characters does not exceed 16 Millions.

输出:

The program should output just an integer corresponding to the number of different substrings of size N found in the given text.
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

样例输入:

1

3 4
daababac

样例输出:

5

主要思路:将出现的字符用nc进制的数来表示,保证其不会重复出现。。若有重复子字符串则这个数就相同,len-n+1 总的子字符串个数。。这个需要仔细观察。hash存储查找一遍重复的–最后就只剩下不重复的子字符串的个数了。

 

#include <stdio.h>
#include <string.h>
#define N 16000007
int hash[8000000],assi[27];
char str[N];
int a[N];
int main()
{
#ifndef ONLINE_JUDGE
	freopen("acm.txt","r",stdin);
#endif
	int T,n,nc,len,k;
	int i,j,sum;
	scanf("%d",&T);
	while(T--)
	{
		memset(hash,0,sizeof(hash));
		scanf("%d %d",&n,&nc);
		getchar();
		scanf("%s",str);
		len=strlen(str);
		i=0;
		k=0;
		for(i = 0; i < len; i++)
		{
			a[i] = str[i] - 'a';
		}
		i = 0;
		while(str[i]!='\0')
		{
			if(assi[a[i]]==0)
				assi[a[i]]=k++;
			if(k==nc)
				break;
			i++;
		}
		int cnt=len-n+1;
		for(i=0;i<len-n+1;i++)
		{
			sum=0;
			for(j=i;j<i+n;j++)
			{
				sum=sum*nc+assi[a[j]];
			}
			sum%=N;
			if(hash[sum]==0)
				hash[sum]=1;
			else
				cnt--;
		}
		printf("%d\n",cnt);
		if(T>0)
			printf("\n");
	}
	return 0;
}

 

解题报告转自:http://blog.csdn.net/vsooda/article/details/8542653


  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  4. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.