글 읽기 - 돌연변이 못풀것네요 substr이 계산이 어떻게되나요?

hswoo8 8년 전 0

stl을 너무많이 써서 계산이 몇번 이뤄지는지 잘모르겠네요;

#include <iostream>
#include <unordered_map>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>

using namespace std;

int main(){
	int t;
	int n, m;				//a의 길이, b의 길이
	string a, b;
	
	scanf_s("%d", &t);

	while (--t >= 0){
		map<string, int> m1;
		scanf_s("%d %d", &n,&m);

		cin >> a >> b;

		for (int i = 0; i < m-1; ++i){
			for (int j = i + 1; j < m; ++j){		//문제		최대 swap 9천번
				swap(b[i],b[j]);
				
				m1.insert(make_pair(b, 0));
				swap(b[i], b[j]);
			}
		}

		int count=0;
		
		for (int j = 0; j < n; ++j){
			if (m1.count(a.substr(j, m))){			//최대 1만번
				
				++count;
			}
		}
		
		cout << count << endl;

	
	}


	return 0;
}

skeksk91 8년 전 0

insert와 count 자체에도 복잡도가 있기 때문에 시간초과가 날것 같습니다.

문자열 자료구조중에 아호코라식 알고리즘을 참고해보세요.

hswoo8 8년 전 0

감사합니다

waninoko 8년 전 0

string을 그냥 cin 하면 아호코라식 써도 시간초과가 나더라구요

그래서 char 배열로 받아서 string 만드는 식으로 했더니 ac받았습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

돌연변이 못풀것네요 substr이 계산이 어떻게되나요?

hswoo8 8년 전 0

skeksk91 8년 전 0

hswoo8 8년 전 0

waninoko 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말