문자 일치 실현

질문:
매우 고 급 스 러 운 문자 매 칭 알고리즘 을 실현 합 니 다: 긴 문자열 을 주 고 요구 에 부합 되 는 문자열 을 찾 아야 합 니 다. 예 를 들 어 목적 문자열: 123 1 * * * * * * * 3 * * * 2, 12 * * * * * * 3 이런 것들 은 모두 찾 아야 합 니 다.
분석:
이 문제 의 진정한 뜻 은 '123' 과 같은 목표 문자열 을 주 는 것 입 니 다. 한 문자열 에 1, 2, 3 이 동시에 포함 되 어 있 으 면 이 문자열 은 일치 합 니 다.시스템 이 조 화 를 이 룰 수록 잘못 죽 일 수도 있다 는 뜻 이다.목표 문자열 의 길 이 는 m 이 고 패턴 문자열 의 길 이 는 n 입 니 다. 우 리 는 O (mn) 의 알고리즘 을 쉽게 생각 할 수 있 습 니 다. 바로 두 번 for 순환 으로 해결 하 는 것 입 니 다 (바로 키 문자열 을 찾 는 것 입 니 다).그렇다면 더 빠 른 방법 은 없 을 까?
   우리 가 문 제 를 고려 할 때 시간 이 빨 라 지 려 면 '공간 이 시간 을 바꾼다' 는 방법 이 있다.해시 표 는 비교적 복잡 한 데이터 구조 이다.비교적 복잡 하기 때문에 STL 에서 해시 표를 실현 하지 못 했 기 때문에 우리 스스로 하 나 를 실현 해 야 한다.그러나 이 문제 의 특수성 때문에 우 리 는 아주 간단 한 해시 표 하나만 있 으 면 요 구 를 만족 시 킬 수 있다.문자 (char) 는 길이 가 8 인 데이터 형식 이기 때문에 모두 256 가지 가능성 이 있 습 니 다.그래서 우 리 는 길이 가 256 인 배열 을 만 들 었 습 니 다. 모든 알파벳 은 ASCII 코드 값 에 따라 배열 의 아래 표 시 는 배열 의 대응 항목 이 고 배열 에 저 장 된 0, 1 은 모든 문자 가 나타 날 지 여부 입 니 다.이렇게 해서 우 리 는 크기 가 256 이 고 문자 ASCII 코드 를 키 로 하 는 해시 표를 만 들 었 다.(영문 문자 에 만 국한 되 는 것 이 아니 므 로 256 가지 가능성 을 고려 해 야 한다).
       이 점 을 알 게 되 었 습 니 다. 우 리 는 하나의 배열 을 구축 하여 패턴 문자열 에 어떤 문자 가 나타 나 는 지 를 통계 한 다음 에 목표 문자열 을 스 캔 하여 해당 하 는 모든 위치 에 나타 나 는 지 확인 하여 일치 하 는 지 판단 할 수 있 습 니 다.복잡 도 를 분석 해 보 세 요. 아마 O (m + n) 일 겁 니 다.
코드 는 다음 과 같 습 니 다:

//       
int is_contain(char *src, char *des)
{
	//       ，    
	const int tableSize = 256;
	int hashTable[tableSize];
	int len,i;

	for(i = 0; i < tableSize; i++)
		hashTable[i] = 0;

	len = strlen(src);
	for(i = 0; i < len; i++)
		hashTable[src[i]] = 1;

	len = strlen(des);
	for(i = 0; i < len; i++)
	{
		if(hashTable[des[i]] == 0)
			return 0;         //    
	}
	return 1;    //    
}