2017 제8 회 블 루 브리지 컵 성 경기 - 대학 A 조 정규 문제 (문자열 처리, dfs)

1564 단어
설명 은 간단 한 정규 표현 식 을 고려 합 니 다. x () | 로 만 구 성 된 정규 표현 식 입 니 다.샤 오 밍 은 이 정규 표현 식 이 받 아들 일 수 있 는 가장 긴 문자열 의 길 이 를 구 하려 고 합 니 다.예 를 들 어 (xx | xxx) x | (x | xx) xx 가 받 아들 일 수 있 는 가장 긴 문자열 은 xxxxx 이 고 길 이 는 6 이다.x () | 로 구 성 된 정규 표현 식 을 입력 하 십시오.입력 길이 가 100 을 초과 하지 않 아 합 법 을 보장 합 니 다.이 정규 표현 식 이 받 아들 일 수 있 는 가장 긴 문자열 의 길 이 를 출력 합 니 다.입력 (xx | xxx) x | (x | xx) xx 출력 6 자원 약정 피크 메모리 소모 (가상 머 신 포함) < 256 M CPU 소모 < 1000 ms 요구 에 따라 엄격하게 출력 하 십시오.메모: main 함 수 는 0 을 되 돌려 야 합 니 다.ANSI C / ANSI C + + 표준 만 사용 하기;컴 파일 환경 이나 운영 체제 에 의존 하 는 특수 함 수 를 호출 하지 마 십시오.모든 의존 함 수 는 원본 파일 에 명확 하 게 있어 야 합 니 다. \ # include 는 프로젝트 설정 을 통 해 상용 헤더 파일 을 생략 할 수 없습니다.프로그램 을 제출 할 때 원 하 는 언어 형식 과 컴 파일 러 형식 을 선택 하 십시오.
사고방식: 한참 동안 추측 하고 나 서 야 이곳 의 | 연산 이 무엇 인지 알 아 보 았 다. 무슨 뜻 인지.이전 다음 의 가장 긴 문자열 을 꺼 냅 니 다.괄호 는 다른 연산 의 괄호 의 뜻 과 같다.
그리고 이 과정 을 어떻게 실현 하 는 지 분석 해 보 세 요.예전 부터 뒤로 옮 겨 다 녔 다.dfs 에 들 어가 면 dfs 에서 튀 어 나 오고 x 를 만나면 x 의 숫자 를 통계 합 니 다.만나다
코드 구현 보기:
#include
#include
#include
using namespace std;
char s[200];
int len = 0,pos = 0; 
int dfs(){
	int xnum = 0;
	int maxx = 0;
	while(pos < len){
		if(s[pos] == '('){
			pos++;
			xnum += dfs();
		}
		else if(s[pos] == ')'){
			pos++;
			break;	
		}
		else if(s[pos] == '|'){
			pos++;
			maxx = max(xnum,maxx);
			xnum = 0;
		}
		else {
			pos++;
			xnum ++;
		}
	}
	maxx = max(xnum,maxx);
	return maxx;
}
int main(){
	cin >> s;
	len = strlen(s);
	int ans = 0;
	ans = dfs();
	printf("%d
",ans); }

좋은 웹페이지 즐겨찾기