I would like to search for substring of string starting from specific index.

Let's say I have string: "PO DAD PO PE DA X PO ZA RA"

Index from which I want to start is character X, so is 13. If I would like to search normally for 'ZA' I would do something like: "DAD PO PE DA X PO ZA RA ZA".indexOf("ZA") and I would get 18.

Next I want to search for first substring 'PO' but backward from "X" index. So, I would get 4 (as it is closer to X from left side) not 15.

How could I do this?

CodePudding user response：

public static void main(String[] args) {
    String s = "PO DAD PO PE DA X PO ZA RA";
    System.out.println(usingSubstring(s));

    
    long start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i  ) {
        usingSubstring(s);
    }
    long end = System.currentTimeMillis();
    System.out.println("`usingSubstring()` took "   (end - start)   "ms.");
}


/**
 * 1. Get the first index of `X`.
 * 2. Substring from 0 ... (1).
 * 3. Get the last index from (2) for `PO`.
 *
 * @param s input string
 * @return last index of `PO` backwards from `X`
 */
private static int usingSubstring(String s) {
    String toSearch = "PO";
    String searchUntil = "X";
    return s.substring(0, s.indexOf(searchUntil)).lastIndexOf(toSearch);
}

Outputs:

7
`usingSubstring()` took 2ms.

Explained in code comments :)

CodePudding user response：

You could implement a custom Iterator for backward search within a String. This, not only will allow you to iterate your String backward, but it will also tell you whether there are further matches or not (via hasNext()) and retrieve all of them with the next() method. The class could contain 3 fields: the string to search, the string to look for and an internal cursor. Through the constructor, you could set the two strings (obviously) and the starting point of the Iterator's cursor.

Here is a possible implementation:

class StringBackwardSearcher implements Iterator<Integer> {
    private String str, match;
    private int index;

    public BackwardSearcher(String str, String match, int index) {
        this.str = Objects.requireNonNull(str);
        this.match = Objects.requireNonNull(match);
        this.index = Objects.checkIndex(index, str.length());
    }

    public void setIndex(int index) {
        this.index = Objects.checkIndex(index, str.length());
    }

    @Override
    public boolean hasNext() {
        return str.substring(0, index).contains(match);
    }

    @Override
    public Integer next() {
        for (; index >= 0; index--) {
            if (str.substring(index - match.length(), index).equals(match)) {
                Integer temp = index;
                index--;
                return temp - match.length();
            }
        }
        return -1;
    }
}

Your main would simply consist of

public static void main(String[] args) {
    String s = "PO DAD PO PE DA X PO ZA RA";
    StringBackwardSearcher bs = new StringBackwardSearcher(s, "PO", 16);
    while (bs.hasNext()) {
        System.out.println(bs.next());
    }
}

If the iterator started at the index of X and had to look for PO, then the output would be:

CodePudding user response：

This should work:

public static int indexOfFromBackOf(String s,String match){
   for(int i = s.length()-1; i>0;i--) {
     int prevI = i;
     boolean found = true;
     for(int j=match.length()-1;j>0 && i>0;j--){
       if(s.charAt(i)!=match.charAt(j)) {found = false; break;}
       else i--;
     }
     if(found) return i;
     i = prevI;
   }
   return -1;
}

and then:

  String s = "DAD PO PE DA X PO ZA RA ZA";
  String match = "PO"; 
  System.out.println(indexOfFromBackOf(s.substring(0,s.indexOf("X")-1),match));

But its messy and complex. why not using Scott's method? in one line:

    String s = "DAD PO PE DA X PO ZA RA ZA";
    String match = "PO";
    String cropped = s.substring(0,s.indexOf("X")-1;
    int index = cropped.length() - (new StringBuilder(cropped).reverse().indexOf(new StringBuilder(match).reverse().toString())   match.length()));

CodePudding user response：

To throw another solution into the mix, one could compile a regular expression with following logic: match starting with "PO", not followed by "PO", and terminated by "X".

In this way, only the closest (from left side) "PO" would match until an "X".

For example:

String subj = "AA PO DAD PO PE DA X PO ZA RA ZA";
        
final Pattern pattern = Pattern.compile("(PO)([^P]|P(?!O))*(X)");
final Matcher matcher = pattern.matcher(subj);
if (matcher.find()) {
   System.err.println("match at ["   matcher.start()   ","   matcher.end()   "): "   matcher.group());
}