私はあなたが言っていることを完全には理解できませんでしたが、例と説明から答えは2 * strlen (string) - 1. これはstrlen (string)、単一の長さの文字列のstrlen (string)数と、指定された文字列からの 2 つの長さの部分文字列の数があるためです。
この質問にはサフィックス ツリーが必要です。ツリーを構築したら、レベル順にトラバースします。次のコードはトリックを行います。それはJavaにあります：
パッケージorg.algocode;
import java.util.ArrayDeque; java.util.Queue をインポートします。
public class TernaryStringCombinator {
private static final int MAX_SIZE = 10000;
public static void main(String[] args) throws Exception {
// Read the input string.
String str = "abac";
if (str == null || str.length() > MAX_SIZE)
throw new Exception(
"Error! Input string is either null or greater than maximum allowed "
+ MAX_SIZE);
// Create the suffix tree
SuffixTree st = new SuffixTree(str);
st.levelOrderTraverse();
// You deduct one here because you don't want to count the root
// placeholder node.
System.out.println("Total nodes in tree " + (st.size() - 1));
// You deduct one here because you don't want to count the original
// string.
System.out.println("Total substrings with only one or two chars "
+ st.size2char());
}
/*
* A suffix tree is a tree of all possible contagious substrings of a
* string. It is a kind of a Trie. For example, for a given input string,
* ABBCD, the tree will store: ABBCD BBCD BCD CD D
*/
private static class SuffixTree {
private Node root;
private String s;
private int size;
private int size2char;
SuffixTree(String s_) throws Exception {
s = s_.toLowerCase();
size2char = s.length();
for (int i = 0; i < s.length(); i++)
insert(s.substring(i));
}
private void insert(String value) throws Exception {
if (root == null) {
root = new Node();
size++;
}
insert(root, value, 0);
}
// This is a recurrsive call to do the insertion
private void insert(Node node, String value, int index)
throws Exception {
Node next = null;
switch (value.charAt(index)) {
case 'a':
if (node.getA() == null)
createChildLink(node, value.charAt(index));
next = node.getA();
break;
case 'b':
if (node.getB() == null)
createChildLink(node, value.charAt(index));
next = node.getB();
break;
case 'c':
if (node.getC() == null)
createChildLink(node, value.charAt(index));
next = node.getC();
break;
default:
throw new Exception("Error! Character is not permitted. "
+ value);
}
if (index < (value.length() - 1)) {
insert(next, value.substring(index + 1), 0);
}
}
void levelOrderTraverse() {
if (root == null || root.isLeaf())
return;
Queue<Node> q = new ArrayDeque<Node>();
if (root.getA() != null)
q.add(root.getA());
if (root.getB() != null)
q.add(root.getB());
if (root.getC() != null)
q.add(root.getC());
while (!q.isEmpty()) {
Node n = (Node) q.poll();
// Only show if path has a color of 0 (two characters). Also the original
// string is not counted as a substring.
if (n.color() == 0) {
if (n.myPath().length() > 1 && !n.myPath().equalsIgnoreCase(s)) {
System.out.println("Two or more char path = "
+ n.myPath());
size2char++;
}
}
if (n.getA() != null)
q.add(n.getA());
if (n.getB() != null)
q.add(n.getB());
if (n.getC() != null)
q.add(n.getC());
}
}
Node root() {
return root;
}
int size() {
return size;
}
int size2char() {
return size2char;
}
private void createChildLink(Node parent, char childVal)
throws Exception {
Node child = new Node(parent, childVal);
size++;
switch (childVal) {
case 'a':
parent.setA(child);
break;
case 'b':
parent.setB(child);
break;
case 'c':
parent.setC(child);
break;
default:
throw new Exception("Error! Character is not permitted. "
+ childVal);
}
}
}
/*
* We will define an inner class to store a suffix tree node. Since it is a
* ternary string, we will have three child nodes of each string.
*/
private static class Node {
private Node parent;
private Node aLink;
private Node bLink;
private Node cLink;
private char value;
private String path;
// Color of a path. 0 if only one or two chars. 1 if all three are
// present in path.
private int color = 0;
Node(Node parent_, char value_) {
value = value_;
parent = parent_;
// Eagerly insert path
path = getPath();
// Eagerly calculate color. If my parent has a 1, then I will
// also be 1. If my parent has 0, then addition of myself can create
// my color to 0. This means that if my parent's path already has
// three
// characters, then I would be on a three character path.
if (parent.color() == 1)
color = 1;
else
colormyself();
}
Node() {
};
void setA(Node aLink_) {
this.aLink = aLink_;
}
void setB(Node bLink_) {
this.bLink = bLink_;
}
void setC(Node cLink_) {
this.cLink = cLink_;
}
Node getParent() {
return parent;
}
Node getA() {
return aLink;
}
Node getB() {
return bLink;
}
Node getC() {
return cLink;
}
char getValue() {
return value;
}
int color() {
return color;
}
// A special method to return combined string of parent
private String getPath() {
if (parent == null)
return null;
String path = parent.myPath();
if (path == null)
return String.valueOf(value);
StringBuilder stb = new StringBuilder();
stb.append(path);
stb.append(value);
return stb.toString();
}
String myPath() {
return path;
}
boolean isLeaf() {
return aLink == null && bLink == null && cLink == null;
}
private void colormyself() {
boolean sawA = false;
boolean sawB = false;
boolean sawC = false;
for (char c : path.toCharArray()) {
switch (c) {
case 'a':
sawA = true;
break;
case 'b':
sawB = true;
break;
case 'c':
sawC = true;
break;
}
if (sawA && sawB && sawC) {
color = 1;
break;
}
}
}
}
}
まず、重複した要素を印刷していることがわかります。文字列のサイズは「n」であると想定しています。したがって、要素が繰り返されても n 要素を出力する必要があります。連続する 2 つの要素については同じなので、'n-1' を使用します。これまでの合計は「2n-1」です。ここで、連続する 2 つの要素を検索し、その合計に「+2」を追加します (前後の文字が null でない場合)。ここで、3 つの連続する要素を検索し、合計で「+3」を追加します。「n」個の重複文字が存在する可能性があるため、「n」までこれを繰り返します。それらをすべて追加します。お役に立てれば。
文字列の長さがn
したがって、結果は次のようになります。2*n-1
文字を 1 つずつ考慮して、入力文字列を反復処理します。各反復で、さまざまなタイプの部分文字列をカウントする 10 個のカウンターを用意します。ポジションを検討しているとしますp。異なるタイプの部分文字列は次のとおりです。
p。resultアルゴリズムが停止すると、答えが含まれるため、私はそれを呼び出しますpposition以降で終わり、 'a' 文字のみを含むもの。と呼ばれるaapposition以降で終わり、 'a' および 'b' 文字のみを含むもの。と呼ばれるabacbabbbccacbccp各カウンターを positionからに更新するのは簡単p+1です。たとえば、 position の文字pが 'a' の場合、次のようになります。
resultで終わるすべての部分文字列を考慮して、すべてのカウンターを に追加します。paaabを追加しますbabを追加しますbaコードフラグメント:
...
int result = 0;
int counters[3][3] = {{0}}; // [0][0] is aa; [0][1] is ab, etc
int L, x, y; // L represents the current Letter; x and y represent other letters
int p; // position in input string
for (p = 0; ; p++)
{
for (y = 0; y < 3; y++)
for (x = 0; x < 3; x++)
result += counters[y][x];
switch (str[p])
{
case 'a': L = 0; x = 1; y = 2; break;
case 'b': L = 1; x = 2; y = 0; break;
case 'c': L = 2; x = 0; y = 1; break;
case '\0': return result;
default: abort();
}
counters[L][L] += 1;
counters[x][L] += counters[x][x] + counters[L][x];
counters[y][L] += counters[y][y] + counters[L][y];
counters[L][x] = 0;
counters[x][x] = 0;
counters[y][x] = 0;
counters[L][y] = 0;
counters[x][y] = 0;
counters[y][y] = 0;
}
奇妙なことに、このコードは string に対して (9 ではなく) 10 を出力し、 string に対してbcabb(17 ではなく) 18を出力しますabbaccb。どの部分文字列が欠落しているかを見つけるための楽しい演習として残します...
static void ternaryStringSubstring(String A){
System.out.println("input ternary string :"+A);
int output = 0;
for(int i=0;i<A.length();i++){
String newStr = "";
for(int j=i+1;j<=A.length();j++){
newStr = A.substring(i, j);
boolean isTernary = true;// Keep track of long loop
List<String> l = new ArrayList<String>();
for(int k=0;k<newStr.length();k++){
String sew = newStr.substring(k, k+1);
if(!l.contains(sew)){
l.add(sew);
}
if(l.size()>2){
isTernary = false;//In case its a long string, it would break
break;
}
}
if(isTernary){
output = output+1;
}
}
}
System.out.println("output :"+output);
}
より最適化されたソリューションについて教えてください