CareerCup

Here's algorithm with worst case o(N^(1+epsilon)) time complexity and O(1) space, where epsilon is arbitrary small constant larger than zero. So algorithm is "almost linear".
The inner loop complexity is O(N) however inner loop runs only d(N) times where d(N) is well-known "divisor function" - number of divisors of N. d(n) = o(N^epsilon), so overall time complexity is o(N*N^epsilon)=o(N^(1+epsilon)).

bool checkPattern(const string& str)
{
	int len = str.size();
	for (int i = 1; i <= len/2; i++) {
		if (len % i == 0) {
			int j = i;
			while (j < len && str[j] == str[j % i]) j++;
			if (j == len) return true;
		}
	}
	return false;
}

This can be done in O(n).

First, create a suffix tree out of the string. Now the problem is reduced to examining the longest branch of the suffix tree. Specifically, we only need to look at the last and second-to-last nodes of the longest branch, because the substring which represents the edge between those two nodes is the only possible option for the repeating substring. This is because if the whole string truly is just a repeated substring, then the longest branch in the suffix tree will branch off (not necessarily only) at equidistant intervals: one branch to continue the longest branch and one branch for the terminating character, eg. $.

Building a suffix tree is O(n).

Now we can simply take that substring we just found and check if the string is really composed of only that string. This is obviously O(n).

The final complexity is this O(2*n) = O(n).

this is classical problem on prefix function

private boolean isPattern(char []a){
		int n = a.length;
                if (n == 0) return true;
		int []p = new int[n];
		for(int i = 1; i < n; ++i){
			int j = p[i-1];
			while(j > 0 && a[j] != a[i]) j = p[j-1];
			if (a[j] == a[i]) ++j;
			p[i] = j;
		}

		// System.out.println(Arrays.toString(p));
		int k = n - p[n-1];
		return p[n-1] > 0 && n % k == 0;
	}

Is the string considered to follow a pattern if it begins or ends with a partial segment? e.g., is xyz the pattern for both "yzxyzxyz" and "xyzxyzx"?

It will begin and ends with same pattern
For xyz it will be: xyzxyz. In terms of regular expression : (xyz)*

I am going to make the java Regex do the work for me:

public static void main(String[] args) {
		String pattern  = "xyz";
		String text = "xyzxyzxyz";
		String [] delimitingStrs = text.split("("+pattern+")+");
		if(delimitingStrs.length == 0)
			System.out.println("Contains the pattern");
		else 
			System.out.println("Does not contain the pattern");
	}

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static boolean patternMatch(char[] s,char[] p)
	{
		boolean isMatched = false;
		
		for(int i=0;i<s.length;)
		{
			System.out.print(" "+i);
			for(int j=0;j<p.length;j++)
			{
				//System.out.print(" "+s[i] );
				if(i< s.length && s[i] == p[j])
				{
				
					
					isMatched = true;
				}
				else
				{
					isMatched = false;
				}
				i++;
				
			}
		 	
		 	//i = i+1;
		}
		
		return isMatched;
	}
	
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		
		System.out.println(" isMatched : "+patternMatch("xyzxyzxyz".toCharArray(),"xyz".toCharArray()));
		System.out.println(" isMatched : "+patternMatch("xyzxyzxyzA".toCharArray(),"xyz".toCharArray()));
	}
	
}

How about this?

bool checkPattern (const string& str) {
	bool is_find = false;
	string pattern1 = ""
	string pattern2 = "";
	int i = 0;
	int j = str.size() - 1;
	while (i >= j) {
		pattern1 += str[i];
		pattern2 = str[j] + pattern2;
		
		if (pattern1 == pattern2) {
			is_find = true;
			break;
		}	
	}
	
	if (is_find) {
		if (str.size() % pattern1.size() != 0) {
			return false;
		} else {				
			for (int i=0; i<str.size(); i+=pattern1.size()) {
				if (pattern1 != str.substr(i,pattern1.size())) {
					return false;
				}			
			}
			return true;		
		}	
	}
}

O(n) algorithm:
the idea is to increment the possible pattern length by 1 and check if you can arrive to the end of the string using that pattern, otherwise you increment patternlength by 1 until patternlength<=s.length/2

- Use two pointers i and j
- Initialize i=0, PatternLength=1, j=i+PatternLength
	while PatternLength<=s.length/2 && j<s.length
		if(s.charAt(i)==s.charAt(j))
			increment i to i=(i+1)%s.length and j to j++
		else
			increment patternlength
			start checking from patternlength+1
	then count the number of repetitions of the pattern in the string by doing j/patternlength,
if patternrepetitions*patternlength==s.length the string is following the pattern.

here is a step by step description of the algorithm for the string "xyzxyzxyz"

Strng s = "xyzxyzxyz";
Step 1:
i=0 j=1
s[i]=x,s[j]=y
PatternLength: 1 PatternRepetitions: 0
Step 2:
i=0 j=2
s[i]=x,s[j]=z
PatternLength: 2 PatternRepetitions: 0
Step 3:
i=0 j=3
s[i]=x,s[j]=x
PatternLength: 3 PatternRepetitions: 0
Step 4:
i=1 j=4
s[i]=y,s[j]=y
PatternLength: 3 PatternRepetitions: 1
Step 5:
i=2 j=5
s[i]=z,s[j]=z
PatternLength: 3 PatternRepetitions: 1
Step 6:
i=0 j=6
s[i]=x,s[j]=x
PatternLength: 3 PatternRepetitions: 2
Step 7:
i=1 j=7
s[i]=y,s[j]=y
PatternLength: 3 PatternRepetitions: 2
Step 8:
i=2 j=8
s[i]=z,s[j]=z
PatternLength: 3 PatternRepetitions: 2

Final Step:
String: xyzxyzxyz
Pattern: xyz
PatternLength: 3 PatternRepetitions: 3

9 steps to check for a string of length 9

This is the code in java to implement this algorithm:

public static boolean followPattern(String s) {
		if(s==null || s.length()==0) return false;
		int i = 0;
		int j = 1;
		int patternlength = 1;
		int repetitions = 0;
		int steps = 1;
		while(patternlength<=s.length()/2 && j<s.length()) {
			if(s.charAt(i)==s.charAt(j)) {
				j++;
				i=(i+1)%patternlength;
				repetitions=j/patternlength;
			}
			else {
				i=0;
				patternlength++;
				j=i+patternlength;
				repetitions=0;
			}
			steps++;
		}
		if(patternlength*repetitions==s.length()) {
			//System.out.println("String: "+s+"\nPattern: "+s.substring(0,patternlength)+"\nPatternLength: "+patternlength+"\nRepetitions: "+repetitions);
			return true;
		}
		else {
			return false;
		}
	}

#include<stdio.h>

int check_pattern(char *str)
{
        int i=0, j=0;
        while(*str)
        {
                if(str[i] != str[j+1])
                        j++;
                else
                {
                        i++;
                        j++;
                        if(str[i] == '\0')
                                return 1;
                }
                str++;
        }
        return 0;
}


int main()
{
        char str[20];
        int res;

        printf("Enter the pattern\n");
        scanf("%s",str);

        res=check_pattern(str);
        if(res == 1 )
                printf("pattern match\n");
        else
                printf("unknown pattern\n");

        return 0;

}
~                                                                                                                                                                                                            
~                                                                                                                                                                                                            
~

import java.util.Scanner;

public class Pattern {
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter a String: ");
String str = sc.nextLine();
boolean status = checkPattern(str);
System.out.println("Given Pattern Status is "+status);

}
static boolean checkPattern(String str)
{
boolean status = false;
char st[] = str.toCharArray();
int length = str.length();
for(int i=0;i<length;i=i+3)
{
if((st[i]=='x')&&(st[i+1]=='y')&&(st[i+2]=='z'))
{
status = true;
continue;
}
else
{
status = false;
break;
}
}
return status;
}
}

This can be done in O(n) complexity using a process similar to calculation of T for the KMP algorithm. If there is a pattern then there should exist a run of ascending values at the end of T with a length at least half the total length of the string. This has the added benefit of not requiring perfectly formed sets of the pattern (ie: 'xyzxyzx' would be positive since it's a repetition of 'xyz').

This is a sample of what I would expect as internal calculations:

Str:	 x   y   z   x  y  z  x  y  z  x
t:      -1  -1  -1   0  1  2  3  4  5  6
true since t ends as >= Str.length() / 2

Str:	x   y   z   d  x   y  z  x  y  z  x
t:     -1  -1  -1  -1  0   1  2  0  1  2  0
false

public static boolean hasPattern(String str){
	//build T
	if(str == null){
		throw new NullPointerException();
	}
	if(str.length() < 2){
		return false;
	}
	int t = -1;
	int i1 = 0;
	int i2 = 1;
	while(i2 < str.length()){
		if(str.charAt(i1) == str.charAt(i2)){
			t++;
			i1++;
		}
		else{
			t = -1;
			i1 = 0;
		}
		i2++;
	}

	//verify correct length
	return (t + 1) >= (str.length() >>> 1);
}

O(m * n)

public boolean checkPattern (String s, String p){
		if (s.length() % p.length() != 0) 
			return false ;
		for (int i = 0 ; s.length() - i >= p.length()  ;  i += p.length()) {
			 int j = 0;
		     while (j < p.length() && s.charAt(i + j) == p.charAt(j)) j++;
		     if (j != p.length()) return false ;
		     
		}					
		return true ;

}