Encuentre índices de todas las ocurrencias de una string en otra

Dadas dos strings, str1 y str2, la tarea es imprimir los índices (Considere, índices a partir de 0) de la ocurrencia de str2 en str1. Si no se produce dicho índice, escriba «NINGUNO».

Ejemplos:

Input : GeeksforGeeks
        Geeks
Output : 0 8

Input : GFG
        g
Output : NONE

Una solución simple es verificar todas las substrings de una string dada una por una. Si una substring coincide, imprime su índice. 

// C++ program to find indices of all
// occurrences of one string in other.
#include <iostream>
using namespace std;
void printIndex(string str, string s)
{
 
    bool flag = false;
    for (int i = 0; i < str.length(); i++) {
        if (str.substr(i, s.length()) == s) {
            cout << i << " ";
            flag = true;
        }
    }
 
    if (flag == false)
        cout << "NONE";
}
int main()
{
    string str1 = "GeeksforGeeks";
    string str2 = "Geeks";
    printIndex(str1, str2);
    return 0;
}

// Java program to find indices of all
// occurrences of one String in other.
class GFG {
 
    static void printIndex(String str, String s)
    {
 
        boolean flag = false;
        for (int i = 0; i < str.length() - s.length() + 1; i++) {
            if (str.substring(i, i + s.length()).equals(s)) {
                System.out.print(i + " ");
                flag = true;
            }
        }
 
        if (flag == false) {
            System.out.println("NONE");
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String str1 = "GeeksforGeeks";
        String str2 = "Geeks";
        printIndex(str1, str2);
    }
}
 
// This code is contributed by Rajput-JI

# Python program to find indices of all
# occurrences of one String in other.
def printIndex(str, s):
 
    flag = False;
    for i in range(len(str)):
        if (str[i:i + len(s)] == s):
             
            print( i, end =" ");
            flag = True;
 
    if (flag == False):
        print("NONE");
         
# Driver code       
str1 = "GeeksforGeeks";
str2 = "Geeks";
printIndex(str1, str2);
 
# This code contributed by PrinciRaj1992

// C# program to find indices of all
// occurrences of one String in other.
using System;
 
class GFG {
 
    static void printIndex(String str, String s)
    {
 
        bool flag = false;
        for (int i = 0; i < str.Length - s.Length + 1; i++) {
            if (str.Substring(i,
                              s.Length)
                    .Equals(s)) {
                Console.Write(i + " ");
                flag = true;
            }
        }
 
        if (flag == false) {
            Console.WriteLine("NONE");
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        String str1 = "GeeksforGeeks";
        String str2 = "Geeks";
        printIndex(str1, str2);
    }
}
 
// This code is contributed by 29AjayKumar

<?php
// PHP program to find indices of all
// occurrences of one string in other.
function printIndex($str, $s)
{
    $flag = false;
    for ($i = 0; $i < strlen($str); $i++)
    {
        if (substr($str,$i, strlen($s)) == $s)
        {
            echo $i . " ";
            $flag = true;
        }
    }
 
    if ($flag == false)
        echo "NONE";
}
 
// Driver Code
$str1 = "GeeksforGeeks";
$str2 = "Geeks";
printIndex($str1, $str2);
 
// This code is contributed by mits
?>

<script>
      // JavaScript program to find indices of all
      // occurrences of one String in other.
      function printIndex(str, s) {
        var flag = false;
        for (var i = 0; i < str.length - s.length + 1; i++) {
          if (str.substring(i, s.length + i) == s) {
            document.write(i + " ");
            flag = true;
          }
        }
 
        if (flag === false) {
          document.write("NONE");
        }
      }
 
      // Driver code
      var str1 = "GeeksforGeeks";
      var str2 = "Geeks";
      printIndex(str1, str2);
</script>

0 8

Complejidad del tiempo: O(n * n)
 

Una solución eficiente es el algoritmo de coincidencia de strings KMP .