poj 1200 Crazy Search

简介:

   给字母编码后,用NC当进制进行hash,或者直接java水过

 

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define INF 1E9
using namespace std;
int N,NC;
char org[1000000];
int hash[10000000];
int v[200];
int find()
{
    int i=0,j=0,now=0,hh,ans=0,len=strlen(org);
    for(i=0,j=0;i<len;i++)
    {
        if(v[org[i]]==0)v[org[i]]=++j;
        if(j==NC)break;
    }
    for(i=0;i<N;i++) now=now*NC+v[org[i]];
    ans++;hash[now]=1;
    int t=pow(NC,N-1);
    for(j=0,i=N;i<len;i++,j++)
    {
        now-=t*v[org[j]];
        now=now*NC+v[org[i]];
        if(hash[now]!=0)continue;
        hash[now]=1;ans++;
    }
    return ans;
}
int main()
{
    scanf("%d%d%s",&N,&NC,org);
    printf("%d\n",find());
    return 0;
}

import java.util.HashMap;
import java.util.Scanner;


public class Main {
	private static Scanner in;

	public static void main(String[] args) {
		HashMap<String, Boolean> vis=new HashMap<String,Boolean>();
		in = new Scanner(System.in);
		@SuppressWarnings("unused")
		int N=in.nextInt(),NC=in.nextInt();
		String s=in.next(),t;
		int i,j,len=s.length(),ans=0;
	    for(i=N,j=0;i<=len;i++,j++)
	    {
	    
	    	t=s.substring(j, i);
	        if(vis.containsKey(t)==true) continue;
	        vis.put(t, true);
	        ans++;
	    }
	    System.out.println(ans);
	}

}


 

import java.util.HashMap;
import java.util.Scanner;


public class Main {
	private static Scanner in;

	public static void main(String[] args) {
		HashMap<String, Boolean> vis=new HashMap<String,Boolean>();
		in = new Scanner(System.in);
		@SuppressWarnings("unused")
		int N=in.nextInt(),NC=in.nextInt();
		String s=in.next(),t;
		int i,j,len=s.length(),ans=0;
	    for(i=N,j=0;i<=len;i++,j++)
	    {
	    
	    	t=s.substring(j, i);
	        if(vis.containsKey(t)==true) continue;
	        vis.put(t, true);
	        ans++;
	    }
	    System.out.println(ans);
	}

}


 

 

目录
相关文章
|
存储
poj 3254 Corn Fields (状态压缩dp)
状态压缩dp其实就是用二进制来表示所有的状态,比如这题, 我们在某一行可以这样取0 1 0 1 1 0 1,用1代表取了,0代表没取,因为这点,它的数据量也限制在20以内,所有看到这样数据量的题目可以先考虑一下状态压缩dp。对于有多行的数据,所有状态的总数必然很庞大,而且不用特殊的方法想要存储这些状态是不太现实的。既然每个点只有这两种情况,我们可以用二进制的一位来表示,0 1 0 1 1 0 1就可以表示为二进制0101101也就是十进制的45,如果我们想要枚举6个点的所有状态,我们只需要从0到2^6取其二进制就可以了,并不会重复或是多余。
34 0
|
7月前
|
机器学习/深度学习 安全 Java
hdu-1596-find the safest road(dijkstra)
hdu-1596-find the safest road(dijkstra)
46 0
poj 2362 hdoj 1518 Square(搜索)
不难了解,小棒子的长度越长,其灵活性越差。例如长度为5的一根棒子的组合方式要比5根长度为1的棒子的组合方式少,这就是灵活性的体现。
54 0
poj 2352 Stars 树状数组
树状数组,简单题,我刚刚开始学的时候就a了,不多说什么了,直接贴代码。
35 0
|
存储 容器
华为机试HJ41:称砝码(深度优先遍历dfs-Depth First Search)
华为机试HJ41:称砝码(深度优先遍历dfs-Depth First Search)
154 0
|
网络架构
POJ 3250 Bad Hair Day、POJ 2796 Feel Good(单调栈)
POJ 3250 Bad Hair Day、POJ 2796 Feel Good(单调栈)