문자열에서 하위 시퀀스의 발생 수 찾기
예를 들어, 문자열을 pi,의 처음 10 자리 숫자로 3141592653, 하위 시퀀스를 123. 시퀀스는 두 번 발생합니다.
3141592653
1 2 3
1 2 3
이것은 제가 대답 할 수없는 인터뷰 질문이었고 효율적인 알고리즘을 생각할 수 없었고 저를 괴롭 히고 있습니다. 간단한 정규식으로 할 수 있어야한다고 생각하지만 1.*2.*3모든 하위 시퀀스를 반환하지는 않습니다. Python에서 내 순진한 구현 (각 1 이후에 각각 2에 대해 3을 계산)은 한 시간 동안 실행되었지만 완료되지 않았습니다.
이것은 고전적인 동적 프로그래밍 문제입니다 (일반적으로 정규 표현식을 사용하여 해결되지 않음).
내 순진한 구현 (각 1 후 각 2에 대해 3을 계산)이 한 시간 동안 실행되었지만 완료되지 않았습니다.
이는 기하 급수적 인 시간에 실행되는 철저한 검색 접근 방식입니다. (나는 그것이 몇 시간 동안 실행된다는 것에 놀랐습니다).
다음은 동적 프로그래밍 솔루션에 대한 제안입니다.
재귀 솔루션의 개요 :
(긴 설명에 대해 사과 드리지만, 각 단계는 정말 간단하므로 저를 참아주세요 ;-)
경우 서브가 비어 일치하는 것이 (더 숫자가 일치하도록 남아 있지!) 우리는 1을 반환
는 IF 입력 순서는 우리가 우리의 자리를 고갈했습니다 아마도 따라서 우리는 0을 반환 일치하는 항목을 찾을 수 없습니다 비우
(시퀀스도 서브 시퀀스도 비어 있지 않습니다.)
( " abcdef "는 입력 시퀀스를 나타내고 " xyz "는 하위 시퀀스를 나타낸다고 가정합니다 .)
result0으로 설정bcdef 및 xyz에
result대한 일치 수에 추가 (즉, 첫 번째 입력 숫자를 버리고 반복)처음 두 자리가 일치하는 경우 (예 : a = x)
- bcdef 및 yz에
result대한 일치 수에 추가 (즉, 첫 번째 하위 시퀀스 숫자와 일치하고 나머지 하위 시퀀스 숫자에서 반복)
- bcdef 및 yz에
반환
result
예
여기에 입력 1221 / 대한 재귀 호출의 그림이다 (12) . (굵은 글꼴의 하위 시퀀스, ·는 빈 문자열을 나타냅니다.)
동적 프로그래밍
순진하게 구현하면 일부 (하위) 문제가 여러 번 해결됩니다 (예 : 위의 그림에서 2). 동적 프로그래밍은 이전에 해결 된 하위 문제 (일반적으로 조회 테이블)의 결과를 기억함으로써 이러한 중복 계산을 방지합니다.
이 특별한 경우에 우리는
- [시퀀스 길이 + 1] 행 및
- [서브 시퀀스 길이 + 1] 열 :
아이디어는 우리가 221 / 대한 일치의 수를 입력해야한다는 것입니다 이 해당 행 / 열에서. 완료되면, 우리는 세포 1221 /에서 최종 솔루션해야한다 (12) .
즉시 알고있는 정보 ( "기본 사례")로 테이블을 채우기 시작합니다.
- 하위 시퀀스 숫자가 남아 있지 않으면 하나의 완전한 일치가 있습니다.
시퀀스 숫자가 남아 있지 않으면 일치하는 항목이 없습니다.
그런 다음 다음 규칙에 따라 테이블을 하향식 / 왼쪽에서 오른쪽으로 채 웁니다.
[ row ] [ col ] 셀 에 [ row -1] [col]에 있는 값을 씁니다 .
직관적으로,이 방법 "221 / 경기 용의 수가 2 21 / 모든 일치 포함하는 2 ."
행 행의 시퀀스 와 열 col의 하위 시퀀스 가 같은 숫자로 시작하는 경우 [ 행 -1] [ col -1] 에서 찾은 값을 [ row ] [ col ]에 방금 쓴 값에 더합니다 .
직관적으로,이 방법은 "1221 /위한 일치의 수 (12)는 또한 221 / 모든 일치 포함한다 (12) ."
최종 결과는 다음과 같습니다.
오른쪽 하단 셀의 값은 실제로 2입니다.
코드에서
파이썬이 아닙니다 (내 사과).
class SubseqCounter {
String seq, subseq;
int[][] tbl;
public SubseqCounter(String seq, String subseq) {
this.seq = seq;
this.subseq = subseq;
}
public int countMatches() {
tbl = new int[seq.length() + 1][subseq.length() + 1];
for (int row = 0; row < tbl.length; row++)
for (int col = 0; col < tbl[row].length; col++)
tbl[row][col] = countMatchesFor(row, col);
return tbl[seq.length()][subseq.length()];
}
private int countMatchesFor(int seqDigitsLeft, int subseqDigitsLeft) {
if (subseqDigitsLeft == 0)
return 1;
if (seqDigitsLeft == 0)
return 0;
char currSeqDigit = seq.charAt(seq.length()-seqDigitsLeft);
char currSubseqDigit = subseq.charAt(subseq.length()-subseqDigitsLeft);
int result = 0;
if (currSeqDigit == currSubseqDigit)
result += tbl[seqDigitsLeft - 1][subseqDigitsLeft - 1];
result += tbl[seqDigitsLeft - 1][subseqDigitsLeft];
return result;
}
}
복잡성
이 "테이블 채우기"접근 방식의 보너스는 복잡성을 파악하는 것이 사소하다는 것입니다. 각 셀에 대해 일정한 양의 작업이 수행되며 시퀀스 길이 행과 하위 시퀀스 길이 열이 있습니다. O (MN)에 대한 복잡성이 있습니다. 여기서 M 과 N 은 시퀀스의 길이를 나타냅니다.
좋은 대답, aioobe ! 답변을 보완하기 위해 Python에서 가능한 몇 가지 구현 :
# straightforward, naïve solution; too slow!
def num_subsequences(seq, sub):
if not sub:
return 1
elif not seq:
return 0
result = num_subsequences(seq[1:], sub)
if seq[0] == sub[0]:
result += num_subsequences(seq[1:], sub[1:])
return result
# top-down solution using explicit memoization
def num_subsequences(seq, sub):
m, n, cache = len(seq), len(sub), {}
def count(i, j):
if j == n:
return 1
elif i == m:
return 0
k = (i, j)
if k not in cache:
cache[k] = count(i+1, j) + (count(i+1, j+1) if seq[i] == sub[j] else 0)
return cache[k]
return count(0, 0)
# top-down solution using the lru_cache decorator
# available from functools in python >= 3.2
from functools import lru_cache
def num_subsequences(seq, sub):
m, n = len(seq), len(sub)
@lru_cache(maxsize=None)
def count(i, j):
if j == n:
return 1
elif i == m:
return 0
return count(i+1, j) + (count(i+1, j+1) if seq[i] == sub[j] else 0)
return count(0, 0)
# bottom-up, dynamic programming solution using a lookup table
def num_subsequences(seq, sub):
m, n = len(seq)+1, len(sub)+1
table = [[0]*n for i in xrange(m)]
def count(iseq, isub):
if not isub:
return 1
elif not iseq:
return 0
return (table[iseq-1][isub] +
(table[iseq-1][isub-1] if seq[m-iseq-1] == sub[n-isub-1] else 0))
for row in xrange(m):
for col in xrange(n):
table[row][col] = count(row, col)
return table[m-1][n-1]
# bottom-up, dynamic programming solution using a single array
def num_subsequences(seq, sub):
m, n = len(seq), len(sub)
table = [0] * n
for i in xrange(m):
previous = 1
for j in xrange(n):
current = table[j]
if seq[i] == sub[j]:
table[j] += previous
previous = current
return table[n-1] if n else 1
이를 수행하는 한 가지 방법은 두 개의 목록을 사용하는 것입니다. 그들 Ones과 OneTwos.
문자열을 문자별로 이동합니다.
- 숫자가 표시 될 때마다 목록에
1항목을Ones작성하십시오. - 당신이 숫자를 볼 때마다
2의 통과Ones목록과에 항목 추가OneTwos목록을. - 당신이 숫자를 볼 때마다
3의 통과OneTwos목록 및 출력123.
일반적으로이 알고리즘은 문자열을 한 번 통과하고 일반적으로 훨씬 작은 목록을 여러 번 통과하므로 매우 빠릅니다. 하지만 병리학적인 경우는 그것을 죽일 것입니다. 와 같은 문자열을 상상해보십시오. 111111222222333333그러나 각 숫자가 수백 번 반복됩니다.
from functools import lru_cache
def subseqsearch(string,substr):
substrset=set(substr)
#fixs has only element in substr
fixs = [i for i in string if i in substrset]
@lru_cache(maxsize=None) #memoisation decorator applyed to recs()
def recs(fi=0,si=0):
if si >= len(substr):
return 1
r=0
for i in range(fi,len(fixs)):
if substr[si] == fixs[i]:
r+=recs(i+1,si+1)
return r
return recs()
#test
from functools import reduce
def flat(i) : return reduce(lambda x,y:x+y,i,[])
N=5
string = flat([[i for j in range(10) ] for i in range(N)])
substr = flat([[i for j in range(5) ] for i in range(N)])
print("string:","".join(str(i) for i in string),"substr:","".join(str(i) for i in substr),sep="\n")
print("result:",subseqsearch(string,substr))
출력 (즉시) :
string:
00000000001111111111222222222233333333334444444444
substr:
0000011111222223333344444
result: 1016255020032
내 빠른 시도 :
def count_subseqs(string, subseq):
string = [c for c in string if c in subseq]
count = i = 0
for c in string:
if c == subseq[0]:
pos = 1
for c2 in string[i+1:]:
if c2 == subseq[pos]:
pos += 1
if pos == len(subseq):
count += 1
break
i += 1
return count
print count_subseqs(string='3141592653', subseq='123')
편집 : 이것은 1223 == 2더 복잡한 경우 에도 정확해야합니다 .
def count_subseqs(string, subseq):
string = [c for c in string if c in subseq]
i = 0
seqs = []
for c in string:
if c == subseq[0]:
pos = 1
seq = [1]
for c2 in string[i + 1:]:
if pos > len(subseq):
break
if pos < len(subseq) and c2 == subseq[pos]:
try:
seq[pos] += 1
except IndexError:
seq.append(1)
pos += 1
elif pos > 1 and c2 == subseq[pos - 1]:
seq[pos - 1] += 1
if len(seq) == len(subseq):
seqs.append(seq)
i += 1
return sum(reduce(lambda x, y: x * y, seq) for seq in seqs)
assert count_subseqs(string='12', subseq='123') == 0
assert count_subseqs(string='1002', subseq='123') == 0
assert count_subseqs(string='0123', subseq='123') == 1
assert count_subseqs(string='0123', subseq='1230') == 0
assert count_subseqs(string='1223', subseq='123') == 2
assert count_subseqs(string='12223', subseq='123') == 3
assert count_subseqs(string='121323', subseq='123') == 3
assert count_subseqs(string='12233', subseq='123') == 4
assert count_subseqs(string='0123134', subseq='1234') == 2
assert count_subseqs(string='1221323', subseq='123') == 5
psh. O (n) 솔루션이 훨씬 좋습니다.
나무를 만들어서 생각해보십시오.
문자가 '1'이면 문자열을 따라 반복하고 트리의 루트에 노드를 추가합니다. 문자가 '2'이면 각 첫 번째 수준 노드에 자식을 추가합니다. 캐릭터가 '3'이면 각 두 번째 수준 노드에 자식을 추가합니다.
세 번째 계층 노드의 수를 반환합니다.
이것은 공간 비효율적이므로 각 깊이의 노드 수를 저장하지 않는 이유는 무엇입니까?
infile >> in;
long results[3] = {0};
for(int i = 0; i < in.length(); ++i) {
switch(in[i]) {
case '1':
results[0]++;
break;
case '2':
results[1]+=results[0];
break;
case '3':
results[2]+=results[1];
break;
default:;
}
}
cout << results[2] << endl;
숫자 배열에서 모든 세 멤버 시퀀스 1..2..3을 계산하는 방법.
빠르고 간단하게
모든 시퀀스를 찾을 필요는 없으며 COUNT 개만 있으면됩니다. 따라서 시퀀스를 검색하는 모든 알고리즘은 지나치게 복잡합니다.
- 1,2,3이 아닌 모든 숫자를 버립니다. 결과는 char 배열 A입니다.
- 병렬 int 배열 B를 0으로 만듭니다. 끝부터 A를 실행하고 A의 각 2를 세고 A의 3의 수를 세십시오. 이 숫자를 B의 적절한 요소에 넣으십시오.
- 0의 병렬 int 배열 C를 만듭니다. A의 각 1에 대한 끝 카운트에서 A를 실행하여 해당 위치 이후 B의 합계입니다. 결과는 C의 적절한 위치에 배치됩니다.
- C의 합을 센다.
그게 다입니다. 복잡성은 O (N)입니다. 실제로 일반 자릿수 줄의 경우 소스 줄이 짧아지는 시간의 약 두 배가 걸립니다.
시퀀스가 M 멤버와 같이 더 길면 절차를 M 번 반복 할 수 있습니다. 그리고 복잡성은 O (MN)가 될 것입니다. 여기서 N은 이미 단축 된 소스 문자열의 길이입니다.
이 문제에 대한 흥미로운 O (N) 시간과 O (M) 공간 솔루션 이 있습니다.
N은 텍스트의 길이이고 M은 검색 할 패턴의 길이입니다. 나는 C ++로 구현하기 때문에 알고리즘을 설명 할 것입니다.
주어진 입력이 3141592653을 제공하고 찾을 수있는 패턴 시퀀스가 123이라고 가정합니다. 먼저 문자를 입력 패턴의 위치에 매핑하는 해시 맵을 사용합니다. 또한 처음에 0으로 초기화 된 크기 M의 배열을 사용합니다.
string txt,pat;
cin >> txt >> pat;
int n = txt.size(),m = pat.size();
int arr[m];
map<char,int> mp;
map<char,int> ::iterator it;
f(i,0,m)
{
mp[pat[i]] = i;
arr[i] = 0;
}
뒤에서 요소를 찾기 시작하고 각 요소가 패턴에 있는지 확인합니다. 해당 요소가 패턴에있는 경우. 뭔가를해야합니다.
이제 내가 2와 이전을 찾으면 뒤에서보기 시작할 때 3을 찾지 못했습니다. 이 2는 우리에게 아무런 가치가 없습니다. 왜냐하면 그 이후에 발견 된 어떤 1도 이러한 시퀀스 12와 123을 형성 할 것이기 때문에 Ryt? 생각한다. 또한 현재 위치에서 2를 찾았으며 이전에 찾은 3으로 만 시퀀스 123을 형성하고 이전에 x 3을 발견하면 x 시퀀스를 형성합니다 (2 이전 시퀀스의 일부가 발견되면) ryt? 따라서 전체 알고리즘은 배열에있는 요소를 찾을 때마다 패턴에있는 위치 j를 확인합니다 (해시 맵에 저장 됨). 나는 단지 증가
arr[j] += arr[j+1];
그것이 ryt 전에 발견 된 3 개의 시퀀스에 기여할 것이라는 의미? j가 m-1이면 단순히 증가시킵니다.
arr[j] += 1;
이러한 작업을 수행하는 아래 코드 스 니펫을 확인하세요.
for(int i = (n-1);i > -1;i--)
{
char ch = txt[i];
if(mp.find(ch) != mp.end())
{
int j = mp[ch];
if(j == (m-1))
arr[j]++;
else if(j < (m-1))
arr[j] += arr[j+1];
else
{;}
}
}
이제 사실을 고려하십시오
each index i in the array stores the number of times the substring of the pattern S[i,(m-1)] appers as a sequence of the input string So finally print the value of arr[0]
cout << arr[0] << endl;
Code with Output(unique chars in pattern) http://ideone.com/UWaJQF
Code with Output(repetitions allowed of chars) http://ideone.com/14DZh7
Extension works only if pattern has unique elements What if pattern has unique elements then complexity may shoot to O(MN) Solution is similar without using DP just when an element occuring in the pattern appeared we just incremented array position j corresponding to it we now have to update all this characters' occurences in the pattern which will lead to a complexity of O(N*maxium frequency of a charater)
#define f(i,x,y) for(long long i = (x);i < (y);++i)
int main()
{
long long T;
cin >> T;
while(T--)
{
string txt,pat;
cin >> txt >> pat;
long long n = txt.size(),m = pat.size();
long long arr[m];
map<char,vector<long long> > mp;
map<char,vector<long long> > ::iterator it;
f(i,0,m)
{
mp[pat[i]].push_back(i);
arr[i] = 0;
}
for(long long i = (n-1);i > -1;i--)
{
char ch = txt[i];
if(mp.find(ch) != mp.end())
{
f(k,0,mp[ch].size())
{
long long j = mp[ch][k];
if(j == (m-1))
arr[j]++;
else if(j < (m-1))
arr[j] += arr[j+1];
else
{;}
}
}
}
cout <<arr[0] << endl;
}
}
반복되는 문자열에서 DP없이 유사한 방식으로 확장 할 수 있지만 복잡성은 더 O (MN)
기반으로 자바 스크립트 대답 동적 geeksforgeeks.org에서 프로그래밍 과에서 답 aioobe :
class SubseqCounter {
constructor(subseq, seq) {
this.seq = seq;
this.subseq = subseq;
this.tbl = Array(subseq.length + 1).fill().map(a => Array(seq.length + 1));
for (var i = 1; i <= subseq.length; i++)
this.tbl[i][0] = 0;
for (var j = 0; j <= seq.length; j++)
this.tbl[0][j] = 1;
}
countMatches() {
for (var row = 1; row < this.tbl.length; row++)
for (var col = 1; col < this.tbl[row].length; col++)
this.tbl[row][col] = this.countMatchesFor(row, col);
return this.tbl[this.subseq.length][this.seq.length];
}
countMatchesFor(subseqDigitsLeft, seqDigitsLeft) {
if (this.subseq.charAt(subseqDigitsLeft - 1) != this.seq.charAt(seqDigitsLeft - 1))
return this.tbl[subseqDigitsLeft][seqDigitsLeft - 1];
else
return this.tbl[subseqDigitsLeft][seqDigitsLeft - 1] + this.tbl[subseqDigitsLeft - 1][seqDigitsLeft - 1];
}
}
'Nice programing' 카테고리의 다른 글
| MSVCP140.dll 누락 (0) | 2020.12.03 |
|---|---|
| Subversion 및 Visual Studio 프로젝트에 대한 모범 사례 (0) | 2020.12.03 |
| JavaScript에서 init () 사용법은 무엇입니까? (0) | 2020.12.03 |
| Mac의 터미널에서 Git 구문 강조 표시 활성화 (0) | 2020.12.03 |
| 맵, 각각, 수집의 차이점은 무엇입니까? (0) | 2020.12.03 |