学步园

这个题巨坑的有没有。。java，so easy。set或者map 就可以过的说。。。

C++是hash。。。结果卡了很久。。。。周赛想了想就没做这个。。。然后把所有的方法都对着写了一遍

这是hash的第一题，其实还不是很明白hash的用法。

题意就是有1-nc个字母【按照字典序】，然后问里面长度为n的互异的子串有几个。

C++代码如下

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define eps 1e-5
const int maxn=20000006;
const int maxm=110037;
#define INF 1000000000
using namespace std;
int mode=100000003;
char s[maxn];
bool vis[maxn];
int asc[257];
int main()
{
    int n,nc;
    scanf("%d%d",&n,&nc);
    scanf("%s",s);
    int ans=0,x=0;
    int len=strlen(s);
    for(int i=0;i<len;i++)
    {
        asc[s[i]]=1;
    }
    for(int i=0;i<256;i++)
    {
        if(asc[i])
            asc[i]=x++;
    }
    for(int i=0;i<len-n+1;i++)
    {
        int f=0;
        for(int j=0;j<n;j++)
            f=f*nc+asc[s[i+j]];
        if(!vis[f])
            ans++,vis[f]=1;
    }
    printf("%d\n",ans);
}

java的map

import java.util.*;

public class Main {

	public static void main(String[] args) {
		
		// TODO Auto-generated method stub
		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		int nc=scan.nextInt();
		String str=scan.next();
		System.out.println(solve(str,n));
	}
	public static int solve(String str,int len)
	{
		int count=0;
		int strl=str.length();
		HashMap<Integer,Integer> letter=new HashMap<Integer,Integer>(100000);
		int hash=0;
		for(int i=0;i<strl-(len-1);i++)
		{
			String temp=str.substring(i,i+len);
			hash=temp.hashCode();
			if(letter.get(hash)==null)
			{
				letter.put(hash, 1);
				count++;
			}
		}
		return count;
		
	}

}

java的set【多谢石大神教我用set】

package contest0518;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class D
{
	public static void main(String[]args)
	{
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt(), nc = scan.nextInt();
		String s = scan.next();
		String [] str = new String[s.length() - n + 1];
		for (int i = 0; i < s.length() - n + 1; i++)
		{
			str[i] = s.substring(i, i + n);
		}
		Set set = new HashSet();
		for (int i = 0; i < s.length() - n + 1; i++)
		{
			set.add(str[i]);
		}
		System.out.println(set.size());
	}
}

代码量。。。。一目了然。。【T_T】