http://acm.timus.ru/problem.aspx?space=1&num=1941

題意：

一個火星文字母是由三個ASCII（從33到122）值一樣的字符組成輸入n個火星文，中間用空格隔開，

第二行再輸入m個火星文，用空格隔開，求m中有多少個連續子串的火星字母組成和n中一樣（包括種類和個數）；

eg:

輸入：

aaa bbb????????????????????????????????????????????????????????? //輸入字符串a

aaa aaa bbb ccc aaa zzz aaa bbb ccc????? //輸入字符串b

輸出：

３

Hint:

Two substrings “aaa bbb ccc” (starting from the second and the seventh positions in the text) and a substring “bbb ccc aaa” are scary for the Martians.

思路：

本題主要是輸入的時候出了問題，因為是連續三個字符相同，則只存一個，剛開始用的gets()，結果在輸入

第二個字符串的時候盡管前面用了getchar()但還是被吃掉了一個字符，雖然我以為這并不影響存儲，但結果

是wa，后改成了一個個字符輸入，把有用的字符不重復存起來；用d1[101]把標記a中的各個字符的個數，

然后再搜索b ，先使b的子串和a的長度相同，用d2[101]標出此時子串中各字母的個數再與d1比較，

若個數和種類都相同，則為符合題意的一個子串，再將這個長度的子串沿b往后移一位，此時只有一個字母移

出和一個字母移入，然后分析這兩個字母給d2[101]帶的變化，計算出來后與d1比較，依此循環……

#include<stdio.h>
#include<string.h>
char c,a[40009],b[4000009];
int d1[101]={0};
int d2[101]={0};
int main()
{
?int i,k=0,s=0,lena,lenb,f=0;
??? for(i=1;scanf("%c",&c);i++)
??? {
???? if(c=='\n')break;
???? if(i%4==1)a[k++]=c;
??? }
??? a[k]='\0';
??
?????? lena=k;
??? k=0;
??? for(i=1;scanf("%c",&c);i++)
??? {
???? if(c=='\n')break;
???? if(i%4==1)b[k++]=c;
??? }
??? b[k]='\0';
??? lenb=k;
???? for(i=0;i<lena;i++)
????? d1[a[i]-'!']++;
?if(lenb<lena)printf("0\n");
?else
?{?
??for(i=0;i<lena;i++)
???d2[b[i]-'!']++;
??for(i=0;i<100;i++)
???if(d1[i]==d2[i])f++;
???if(f==100)s++;
???for(i=1;i<=lenb-lena;i++)
???{
????if(d2[b[i-1]-'!']==d1[b[i-1]-'!'])f--;
????else
????if(d2[b[i-1]-'!']==d1[b[i-1]-'!']+1)f++;
????d2[b[i-1]-'!']--;
????d2[b[i+lena-1]-'!']++;
????if(d2[b[i+lena-1]-'!']==d1[b[i+lena-1]-'!'])f++;
????else
????if(d2[b[i+lena-1]-'!']==d1[b[i+lena-1]-'!']+1)f--;
????if(f==100)s++;
???}
???printf("%d\n",s);
?}
?return 0;
}

?

　

?

?

?

?

總結

以上是生活随笔為你收集整理的1941 Scary Martian Word的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。