Вот мой КОД :
#include<iostream>
typedef long long ll;
ll fun(std::string s,ll visited[256],ll n,ll L[]){
ll ans=0;
if(n<0){
return 1;
}
//std::cout<<s.substr(0,n+1)<<" "<<n<<endl;
ans=fun(s,visited,n-1,L);
L[n]=ans;
ans=ans*2;
if(visited[int(s[n])]>=0){
ans -= L[visited[int(s[n])]];
}
visited[int(s[n])]=n;
return ans;
}
int main(){
std::string s;
std::cin>>s;
ll n=s.length();
ll visited[256];
ll L[n];
memset(visited,-1,sizeof(visited));
memset(L,-1,sizeof(L));
std::cout<<fun(s,visited,n-1,L);
return 0;
}
Объяснение :
Я сканирую от конца строки, т. Е. От последнего элемента до первого, и поэтому отправляю первые n-1 символов для дальнейшего сканирования в рекурсии.
Однажды n==-1 or n<0(both are same) я беру пустую строку и возвращаю 1, потому что нет. подпоследовательностей пустой строки равен 1.
Итак, возвращаясь из рекурсии, мы знаем, что добавление текущего неповторяющегося символа к предыдущей строке удваивает число no. подпоследовательностей. Удвоение происходит потому, что теперь я могу добавить этот символ в конце всех предыдущих подпоследовательностей. Итак, with и without этот символ означает двойное число всех предыдущих подпоследовательностей.
Предполагая, что текущий символ не является дубликатом, я умножаю предыдущий номер. подпоследовательностей с 2.
После полного номера из подпоследовательностей первых n-1 символов был вычислен, мы удваиваем их для первых n символов.
Но предположим, что встречающийся в настоящее время символ (n-й символ) уже присутствовал в первых n-1 символах ранее (т. Е. Находится в строке s [0 .... n-1] (примечание: s [n] ] является текущим символом)), тогда мы должны вычесть те, нет. подпоследовательностей, возможных вплоть до (исключая) той части s, когда в последний раз встречался этот текущий символ и который уже был вычислен и сохранен в L ['этот конкретный символ'].
т.е. - BACA - для данной строки 4-й A уже встречался ранее (при возвращении из рекурсии мы сначала сталкиваемся с B, затем A, затем C и, наконец, A) и поэтому мы вычитаем нет. из подпоследовательностей, рассчитанных до (исключая) 2-го A (что равно 2 (потому что число подпоследовательности до A равно 2)).
Итак, каждый раз, когда мы вычисляли нет. подпоследовательностей для первых n-1 символов мы храним их в массиве L.
Примечание : L [k] сохранить номер. подпоследовательностей перед индексом k.
Я использовал массив посещений, чтобы проверить, просканирован ли данный символ, в котором я сейчас присутствую, или нет.
При обнаружении текущего символа я обновляю посещенный массив с позицией текущей позиции как n. Это нужно сделать, потому что мы должны исключить повторяющиеся последовательности.
Примечание : visited[] инициализируется со всеми -1, поскольку позиция любого символа в строке s неотрицательна (индексация на основе 0).
Краткое описание
How do you arrive at the number of duplicates? Let's say the last occurrence of current character at i, was at j'th position. Then, we will have duplicate subsequences: consider starting with i'th character and then all subsequences possible from [0,j-1] vs. starting at j'th character and then all subsequences possible from [0,j-1]. So, to eliminate this, you subtract the number of subsequences possible from upto (excluding) j with L[0]=1 mean that upto(excluding 0), no. of subseq are 1(empty string has 1 subsequence).