Hyper Strings
Problem Statement :
String A is called a Super String if and only if: A contains only letters a,b,c,d,e,f,g,h,i,j; For any i and j, A[i] has lower ascii code than A[j], where 0 < i < j < length(A) Given a set of Super Strings H, a Hyper String is a string that can be constructed by concatenation of some Super Strings of the set H. We can use each Super String as many times as we want. Given set H, you have to compute the number of Hyper Strings with length no greater than M. Input Format The first line of input contains two integers, N(the number of Super Strings in H) and M. The next N lines describe the Super Strings in set H. Constraints N and M are not greater than 100. Output Format Output an integer which is the number of possible Hyper Strings that can be derived. Since it may not fit in 32 bit integer, print the output module 1000000007. (i.e. answer = answer % 1000000007)
Solution :
Solution in C :
In C++ :
#include <algorithm>
#include <functional>
#include <iterator>
#include <numeric>
#include <limits>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
using namespace std;
#define REP(i, n) for (int (i) = 0, __n = (int)(n); (i) < __n; ++(i))
#define REPS(i, s, n) for (int (i) = (s), __n = (int)(n); (i) < __n; ++(i))
#define REPD(i, n) for (int (i) = (n); (i) >= 0; --(i))
#define FOREACH(i, x) for (auto i = (x).begin(); i != (x).end(); ++i)
#define SIZE(x) (int)((x).size())
const int MOD = 1000000007;
const int MAXL = (1<<10);
const int MAXN = 100;
const int MAXM = 100;
string S[MAXN];
int64_t memo[MAXM+1][MAXL];
int ways[MAXL], A[MAXN], lo[MAXN], len[MAXN];
int N, M;
inline int lobit(int x) {
for (int p = 0; x > 0; x >>= 1, ++p)
if (x & 1) return p;
return -1;
}
inline int hibit(int x) {
int res = -1;
for (int p = 0; x > 0; x >>= 1, ++p)
if (x & 1) res = p;
return res;
}
int count_ways(int s) {
string X;
for (int i = 0; s > 0; s >>= 1, ++i)
if (s & 1) X += 'a' + i;
int L = X.length();
vector<int> dp(L+1, 0);
dp[0] = 1;
REPS(i, 1, L+1) {
REP(j, N) {
if ((int)S[j].length() > i) continue;
if (X.substr(i - S[j].length(), S[j].length()) != S[j]) continue;
dp[i] += dp[i - S[j].length()];
}
}
return dp[L];
}
int64_t solve(int m, int last) {
if (m > M) return 0;
int64_t& res = memo[m][last];
if (res != -1) return ways[last] > 1 ? 0 : res;
int hi = hibit(last); res = 1;
REP(i, N) {
int64_t val = 0;
if (ways[A[i]] > 1) continue;
if (lo[i] <= hi) val = solve(m + len[i], A[i]);
else val = solve(m + len[i], A[i] | last);
res = (res + val) % MOD;
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin >> N >> M;
REP(i, N) {
cin >> S[i]; int x = 0;
FOREACH(it, S[i]) x |= (1 << (*it - 'a'));
A[i] = x; lo[i] = lobit(x); len[i] = S[i].length();
}
REPS(s, 1, MAXL) ways[s] = count_ways(s);
memset(memo, -1, sizeof(memo));
cout << solve(0, 0) << "\n";
return EXIT_SUCCESS;
}
In Java :
import java.util.*;
public class Solution
{
int N,M;
boolean[] source=new boolean[1 << 10];
int[] bin=new int[20];
long[][] dp=new long[110][12];
int[][][] ok=new int[10][10][11];
boolean[] state=new boolean[1 << 10];
boolean[] vis=new boolean[1 << 10];
final int mod=1000000007;
boolean State(int s)
{
//if (s==0) return true;
if (vis[s]) return state[s];
vis[s]=true;
if (source[s])
{
state[s]=source[s];
}
else
{
state[s]=false;
int tmp=0;
for (int i=0;i<10;i++)
{
if ((bin[i] & s)!=0)
{
tmp+=bin[i];
if (source[tmp] && State(s-tmp))
{
state[s]=true;
break;
}
}
}
}
return state[s];
}
void build()
{
bin[0]=1;
for (int i=1;i<=12;i++) bin[i]=bin[i-1] << 1;
}
void init()
{
Scanner scan=new Scanner(System.in);
N=scan.nextInt();
M=scan.nextInt();
for (int i=1;i<=N;i++)
{
String str=scan.next();
int tmp=0;
for (int j=0;j<str.length();j++)
{
tmp+=bin[str.charAt(j)-'a'];
}
source[tmp]=true;
}
for (int i=0;i<10;i++) dp[0][i]=0;
dp[0][9]=1;
for (int i=0;i<(1 << 10);i++)
{
if (!State(i)) continue;
int from=11;
int to=-1;
int cnt=0;
for (int j=0;j<10;j++)
{
if ((bin[j] & i)!=0)
{
cnt++;
from=Math.min(from, j);
to=Math.max(to,j);
}
}
ok[from][to][cnt]++;
}
}
void work()
{
for (int i=1;i<=M;i++)
{
for (int j=0;j<10;j++)
{
dp[i][j]=0;
for (int k=1;k<=10;k++)
{
if (i-k<0) break;
for (int l=0;l<10;l++)
{
for (int m=0;m<=l;m++)
{
//if (ok[m][j][k])
{
dp[i][j]+=dp[i-k][l]*ok[m][j][k];
dp[i][j]%=mod;
}
}
}
}
}
}
int result=0;
for (int i=0;i<=M;i++)
{
for (int j=0;j<10;j++)
{
result+=dp[i][j];
result%=mod;
}
}
System.out.println(result);
}
void run()
{
build();
init();
work();
}
public static void main(String[] args)
{
new Solution().run();
}
}
In C :
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define XXX 1
#define MOD (1000000007)
#define NMAX 100
#define MMAX 100
#define SMAX 11
char s[NMAX][SMAX];
int lens[NMAX];
int count[SMAX];
unsigned long long nways[MMAX+1];
// Return 1 if str is a concatenation of other strings in the list
int match(char *str, int n, int N)
{
int i = 0;
int ns;
if (n==0)
return 1; // This string is composite
for (i=0; i<N; i++) {
if (str!=s[i]
&& (ns = lens[i]) <= n
&& ns != 0
&& strncmp(str, s[i], ns)==0
&& match(str+ns, n-ns, N)) {
return 1;
}
}
return 0;
}
// Count the ways of generating string length m (fills cache, nways[])
unsigned long long countways(int m)
{
int i;
unsigned long long ways=0;
if (nways[m]!=0)
return nways[m];
for (i=1; i<SMAX && i<=m; i++)
ways = (ways + count[i]*countways(m-i))%MOD;
nways[m] = ways;
return ways;
}
int main(void)
{
int N, M;
int i;
unsigned long long total;
scanf("%d %d\n", &N, &M);
// Read input super strings
for (i=0; i<N; i++) {
scanf("%s", s[i]);
lens[i] = strlen(s[i]);
}
// Eliminate strings that are composites of shorter strings
for (i=0; i<N; i++)
if (match(s[i], lens[i], N))
lens[i] = 0;
// Count strings of each length
for (i=0; i<SMAX; i++)
count[i] = 0;
for (i=0; i<N; i++)
++count[lens[i]];
// Initialise the cache
nways[0] = 1;
for (i=1; i<=M; i++)
nways[i] = 0;
// Fill the cache
(void)countways(M);
total = 0;
for (i=0; i<=M; i++)
total += nways[i];
printf("%llu\n", total%MOD);
return 0;
}
In Python3 :
from collections import Counter
j,k = map(int, input().split())
supers_list = []
for i in range(j):
supers_list.append(input())
def check_concat(Str_, Sub_Str_):
if Sub_Str_ == "":
return False
for i in supers_list:
if i == Sub_Str_ and Str_ != Sub_Str_:
return True
x = Sub_Str_.startswith(i)
if x == True:
if check_concat(Str_, Sub_Str_[len(i):]) == True:
return True
return False
def filter_():
tmp = []
global supers_list
for i in supers_list:
if check_concat(i,i) == False:
tmp.append(i)
supers_list = tmp
filter_()
y = Counter(len(i) for i in supers_list)
saved = {}
def f(x):
if x in saved: return saved[x]
if x<1: return 0
k = y[x] if x in y else 0
for i in y:
k += y[i]*f(x-i)
saved[x] = k
return k
x = 0
for i in range(1,k+1):
x+=f(i)
print((x+1)%1000000007)
View More Similar Problems
Array Manipulation
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu
View Solution →Print the Elements of a Linked List
This is an to practice traversing a linked list. Given a pointer to the head node of a linked list, print each node's data element, one per line. If the head pointer is null (indicating the list is empty), there is nothing to print. Function Description: Complete the printLinkedList function in the editor below. printLinkedList has the following parameter(s): 1.SinglyLinkedListNode
View Solution →Insert a Node at the Tail of a Linked List
You are given the pointer to the head node of a linked list and an integer to add to the list. Create a new node with the given integer. Insert this node at the tail of the linked list and return the head node of the linked list formed after inserting this new node. The given head pointer may be null, meaning that the initial list is empty. Input Format: You have to complete the SinglyLink
View Solution →Insert a Node at the head of a Linked List
Given a pointer to the head of a linked list, insert a new node before the head. The next value in the new node should point to head and the data value should be replaced with a given value. Return a reference to the new head of the list. The head pointer given may be null meaning that the initial list is empty. Function Description: Complete the function insertNodeAtHead in the editor below
View Solution →Insert a node at a specific position in a linked list
Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e
View Solution →Delete a Node
Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo
View Solution →