POJ 1200

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 int hash[30];
 7 bool loc[20000000];
 8 char str[1000000];
 9 
10 int main()
11 {
12     int n,m,cnt,sum,len,ans,i,j;
13     while(scanf("%d%d",&n,&m)!=EOF)
14     {
15         memset(loc,0,sizeof(loc));
16         memset(hash,0,sizeof(hash));
17         scanf("%s",str);
18         len=strlen(str);
19         cnt=1;
20         ans=0;
21         for(i=0;i+n<=len;i++)
22         {
23             sum=0;
24             for(j=i;j<i+n;j++)
25             {
26                 if(!hash[str[j]-'a'])
27                 {
28                     hash[str[j]-'a']=cnt++;
29                 }
30                 sum*=m;
31                 sum+=hash[str[j]-'a'];
32             }
33             if(!loc[sum])
34             {
35                 loc[sum]=1;
36                 ans++;
37             }
38         }
39         printf("%d\n",ans);
40     }
41     return 0;
42 }

View Code

 1 //ＴＬＥ,搞成单次输入也TLE,也许字符种类数没有用上
 2 //Huge input,scanf is recommended.
 3 #include <iostream>
 4 #include <set>
 5 #include <string>
 6 using namespace std;
 7 
 8 int main()
 9 {
10      int i,j,k,T;
11      int m,n;
12      string s;
13      set <string > sset;
14      while(cin>>m>>n)
15      {
16           s.clear();
17           sset.clear();
18           cin>>s;
19           int len = s.length();
20           for(i=0;i<=len-m;i++)
21           {
22                string temp = s.substr(i,m);
23                sset.insert(temp);
24           }
25           cout<<sset.size()<<endl;
26      }
27      return 0;
28 }
29                
30           
31

View Code

 1 //tle
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <set>
 6 using namespace std;
 7 
 8 char str[16000010] ;
 9 char hash[300];
10 
11 int main()
12 {
13     int n,m,sum,len;
14     int i,j,k,t;
15     set <int > sset;
16     while(scanf("%d%d",&n,&m)==2)
17     { 
18         memset(str,0,sizeof(str));
19         memset(hash,0,sizeof(hash));
20         sset.clear();
21         scanf("%s",str);
22         int cnt = 1;
23         for(i=0;str[i+n-1]!='\0';i++)//不用strlen是为节省时间 
24         {
25             sum=0;
26             for(j=i;j<i+n;j++)
27             {
28                 if(!hash[str[j]-'a'])
29                 {
30                     hash[str[j]-'a']=cnt++;
31                 }
32                 sum = sum*m + hash[str[j]-'a'];
33             }
34             sset.insert(sum);
35         }
36         printf("%d\n",sset.size());
37     }
38     return 0;
39 }

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <map>
 5 using namespace std;
 6 
 7 char str[16000010] ;
 8 char hash[300];
 9 
10 int main()
11 {
12     int n,m,sum,len;
13     int i,j,k,t;
14     map <int,bool > mm;
15     scanf("%d%d",&n,&m);
16     { 
17         int ans  = 0;
18         memset(str,0,sizeof(str));
19         memset(hash,0,sizeof(hash));
20         mm.clear();
21         scanf("%s",str);
22         int cnt = 1;
23         for(i=0;str[i+n-1]!='\0';i++)//不用strlen是为节省时间 
24         {
25             sum=0;
26             for(j=i;j<i+n;j++)
27             {
28                 if(!hash[str[j]-'a'])
29                 {
30                     hash[str[j]-'a']=cnt++;
31                 }
32                 sum = sum*m + hash[str[j]-'a'];
33             }
34             //if(!mm.count(sum))
35             if(!mm[sum])//军超时 
36             {
37                mm[sum] = 1;
38                ans ++;
39             }
40         }
41         printf("%d\n",ans);
42     }
43     return 0;
44 }