Вот еще одна проблема spoj, которая спрашивает, как найти количество отдельных подпоследовательностей строки?
Например,
Вход
AAA
ABCDEFG
CODECRAFTВыход
4
128
496
Как я могу решить эту проблему?
Вот еще одна проблема spoj, которая спрашивает, как найти количество отдельных подпоследовательностей строки?
Например,
Вход
AAA
ABCDEFG
CODECRAFTВыход
4
128
496
Как я могу решить эту проблему?
Это классическая проблема динамического программирования.
Пусть:
dp[i] = number of distinct subsequences ending with a[i]
sum[i] = dp[1] + dp[2] + ... + dp[i]. So sum[n] will be your answer.
last[i] = last position of character i in the given string.
В нулевой строке есть одна подпоследовательность, поэтому dp[0] = 1
.
read a
n = strlen(a)
for i = 1 to n
dp[i] = sum[i - 1] - sum[last[a[i]] - 1]
sum[i] = sum[i - 1] + dp[i]
last[a[i]] = i
return sum[n]
Объяснение
dp[i] = sum[i - 1] - sum[last[a[i]] - 1]
Изначально предположим, что мы можем добавить a[i]
ко всем подпоследовательностям, заканчивающимся предыдущими символами, но это может нарушить условие, что подсчитанные подпоследовательности должны быть разными. Помните, что last[a[i]]
дает нам последнюю позицию a[i]
, появившуюся до сих пор. Единственные подпоследовательности, которые мы используем, - это те, к которым добавлен предыдущий a[i]
, поэтому мы их вычитаем.
sum[i] = sum[i - 1] + dp[i]
last[a[i]] = i
Обновите эти значения в соответствии с их определением.
Если индексирование начинается с 0, используйте a[i - 1]
везде, где я использовал a[i]
. Также не забудьте обернуть ваши вычисления в функцию mod
, если вы собираетесь отправить код. Это должно быть выполнено следующим образом:
mod(x) = (x % m + m) % m
Чтобы правильно обрабатывать отрицательные значения на некоторых языках (например, C/С++).
Существует более простое решение этой проблемы.
Идея такова: если все символы строки различны, общее количество подпоследовательностей равно 2^n.
Теперь, если мы найдем какой-либо символ, который уже встречался ранее, мы должны рассмотреть только его последнее вхождение (иначе последовательность не будет отличной). Таким образом, мы должны вычесть количество подпоследовательностей из-за его предыдущего появления.
Моя реализация такова:
read s
dp[0] = 1
len = strlen(s)
last[s.length()] = {-1} //declaring 'last' array with same as length of string 's' and all elements initialized with -1.
for (i = 1; i <= len; i++)
{
dp[i] = (dp[i - 1] * 2)
if (last[s[i]] > 0) dp[i] = (dp[i] - dp[last[s[i]] - 1])
last[s[i]] = i
}
Вот мой КОД:
#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;
}
Пояснение:
Я сканирую от конца строки ie- от последнего элемента до первого и поэтому отправляю первые n-1
для дальнейшего сканирования в рекурсии.
Как только n==-1 or n<0(both are same)
, я n==-1 or n<0(both are same)
пустую строку и возвращаю 1, потому что нет. подпоследовательностей пустой строки равен 1.
Итак, возвращаясь из рекурсии, мы знаем, что добавление текущего неповторяющегося символа к предыдущей строке удваивает число no. подпоследовательностей. Удвоение происходит потому, что теперь я могу добавить этот символ в конце всех предыдущих подпоследовательностей. Таким образом, with
и without
этого символа означает двойной из всех предыдущих подпоследовательностей.
Предполагая, что текущий символ не является дубликатом, я умножить предыдущий нет. подпоследовательностей с 2.
После общего количества из подпоследовательностей первых n-1
символов было вычислено, мы удваиваем их для первых n
символов.
Но предположим, что встречающийся в настоящее время символ (n-й символ) уже присутствовал в первых n-1
символах ранее (т. n-1
- обнаружен в строке s [0.... n -1] (Примечание: s [n] это текущий символ)), то надо вычесть тех нет. из подпоследовательностей, возможных вплоть до (исключая) той части s, когда в последний раз встречался этот текущий символ и которая уже была вычислена и сохранена в L ['этот конкретный символ'].
то есть - BACA
- для данной строки, 2-й A
уже встречался ранее (возвращаясь из рекурсии, мы сначала сталкиваемся с B
, затем A
, затем C
и, наконец, A
), и поэтому мы вычитаем no. из подпоследовательностей, вычисленных до (исключая) 2-й A
(который равен 2 (количество подпоследовательностей до A
равно 2)).
Таким образом, каждый раз, когда мы рассчитали нет. подпоследовательностей для первых n-1
символов, мы храним их в массиве L.
Обратите внимание: L [K] сохранить номер. подпоследовательностей перед k-м указателем.
Я использовал массив посещений, чтобы проверить, просканирован ли данный символ, в котором я сейчас присутствую, или нет.
При обнаружении текущего символа я обновляю посещенный массив с позицией текущей позиции как n
. Это нужно сделать, потому что мы должны исключить повторяющиеся последовательности.
Примечание: visit visited[]
инициализируется со всеми -1, поскольку позиция любого символа в строке s
неотрицательна (индексирование на основе 0).
Резюме:
How do you arrive at the number of duplicates? Let 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).
///i get wa
int finding_dist_subs(int len,char data[])
{
dp[0]=1;
for(int i=1;i<len;i++)
{
dp[i]=(dp[i-1]*2+1)%1000000007;
for(int j=i-1;j>=0;j--)
{
if(data[i]==data[j])
{
if(j!=0)
dp[i]=(dp[i]-(dp[j-1])-1)%1000000007;
else dp[i]=(dp[i]-1)%1000000007;
break;
}
}
}
return dp[len-1];
}