package com.freetymekiyan.algorithms.level.easy;

import org.junit.Assert;
import org.junit.Test;

/**
 * Implement strStr().
 * <p>
 * Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
 * <p>
 * Company Tags: Pocket Gems, Microsoft, Apple, Facebook
 * Tags: Two Pointers, String
 * Similar Problems: (H) Shortest Palindrome
 */
public class ImplementStrStr {

    /**
     * Two pointers.
     * For each point in haystack, check there is needle.
     * Special case:
     * If needle is empty, return 0.
     */
    public int strStr(String haystack, String needle) {
        if (needle.isEmpty()) {
            return 0;
        }
        int m = haystack.length();
        int n = needle.length();
        for (int i = 0; i <= m - n; i++) {
            for (int j = 0; j < n; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }
                if (j == n - 1) {
                    return i;
                }
            }
        }
        return -1;
    }

    @Test
    public void testExamples() {
        String str1 = "14531234";
        String str2 = "123";
        String str3 = "1123";
        String str4 = "1245";
        String str5 = "12121212123";
        Assert.assertEquals(4, strStr(str1, str2));
        Assert.assertEquals(1, strStr(str3, str2));
        Assert.assertEquals(-1, strStr(str4, str2));
        Assert.assertEquals(8, strStr(str5, str2));
    }
}

@@ -429,17 +429,17 @@
   * Two 
-p
+P
 ointers.
@@ -454,53 +454,173 @@
 For 
-each point in haystack, check
+i from 0 to m-n:%0A     * %7C For j from 0 to n-1:%0A     * %7C   If characters are not the same, break%0A     * %7C   If j reaches
  the
-re is needle
+ end of needle, return i.%0A     * Return -1
 .%0A  
@@ -664,16 +664,40 @@
 s empty,
+ no need to check , just
  return 
@@ -933,24 +933,96 @@
  - n; i++) %7B
+ // Why m-n? From m-n+1 to m-1 the characters are not enough for needle.
 %0A           

update implement strstr()