大衆評価2013技術部実習アルゴリズム問題

912 ワード

大衆評価2013技術部実習アルゴリズム問題
質問:この2つの文字列が等しいかどうかをすばやく比較するにはどうすればいいですか?
2つの文字列が等しい条件は、文字列の各文字が現れる回数が等しいことです.例えば、abbcdとacdbbは等しい.aはいずれも1回、bはいずれも2回、cはいずれも1回、dはいずれも1回であるからである.
方法:hashを利用する.
コードは次のとおりです.
#include<iostream>
#include<string.h>
using namespace std;

void compare(char *a,char *b)
{
  int i=strlen(a);
  int j=strlen(b);
  int k;
  int hash[128]={0};
  if(i!=j)
	  cout<<"     ,      "<<endl;
  char *aString=a;
  char *bString=b;
  while(*(aString)!='\0')
	  hash[*(aString++)]++;
  while(*(bString)!='\0')
	  hash[*(bString++)]--;
  for(k=0;k<128;k++)
  {
    if(hash[k]!=0)
	{
		cout<<"      "<<endl;
		return;
	}
	
  }
  cout<<"     "<<endl;
}

int main()
{
  char *stringA="abbcd";
  char *stringB="acdbb";
  compare(stringA,stringB);
  return 0;
}