Алгоритм поиска подстроки
 

function subStr(_substring, _string) {
	var substring = _substring.split(''),
		string = _string.split(''),
		found = false, k = 1;
	for(var i = 0; i < string.length; i++) {
		if(string[i] == substring[0]) {
			for(var j = 1, l = i + 1; j < substring.length; j++, l++) if (string[l]) {
				if(string[l] == substring[j]) {
					k++;
				} else {
					k = 1;
					break;
				}
			}
			if(k == substring.length) {
				found = true;
				break;
			} else {
				i = l;
			}				
		}
	}
	return found;
}

Можно ли сделать эффективнее? Интересует чисто с академической, так сказать, стороны :)

а чем вам indexOf не угодил?

var string = 'qwe';
var substring = 'we';

alert(string.indexOf(substring) !== -1 ? 'found' : 'not found');

devote,
ну про стандартные конструкции языка я в курсе, интересует именно со стороны эффективности алгоритма. Ну представим на минуту, что в javascript`e отсутствуют стандартные способы поиска подстроки и необходимо его реализовать.
Я вот тут ещё что подумал - к символу строки ведь можно обратиться по индексу, правильно ли я понимаю, что движок в этом случае при каждом подобном обращении преобразует строку к массиву? Целесообразно ли я в начале функции сам преобразовываю строки в массивы :-?

легко:

function strpos(substring, string) {
    return string.split(substring).length === 2;
}
alert(strpos('привет', 'привет мир!'));

вариант 2:

function strpos(substring, string) {
    var index = 0, subindex = 0;
    while(subindex < substring.length && index < string.length) {
        if (substring[subindex] === string[index]) {
           subindex++;
        } else {
           index -= subindex;
           subindex = 0;
        }
        index++;
    }
    return subindex > 0;
}
alert(strpos('привет', 'привет мир!'));

Чет ты перемудрил.

function stringContains(string, substring) {
    if (substring.length === 0)
        return false;
    for (var i = 0; i < string.length; i++) {
        if (string[i] === substring[0]) {
            for (var j = 1; j < substring.length; j++) {
                if (string[i + j] !== substring[j])
                    return false;
            }
            return true;
        }
    }
    return false;
}

Может я тоже)

да вы оба мудрите странно))) без обид

P.S. конечно название я не совсем правильное функций сделал, но это сами придумывайте.

danik.js,
хотя не, у тебя тоже вполне компактно

Дзен-трансгуманист,
ну тогда релиз:

function strpos(substring, string) {
    var index = 0, subindex = 0;
    var subStrLen = substring.length;
    var strLen = string.length;
    while(subindex < subStrLen && index < strLen) {
        if (substring.charCodeAt(subindex) === string.charCodeAt(index)) {
            subindex++;
        } else {
            index -= subindex;
            subindex = 0;
        }
        index++;
    }
    return subindex > 0;
}
alert(strpos('привет', 'привет мир!'));

частое обращение к свойству .length тоже влияет на производительность.

Хром 28, разница чуть меньше: x8

zilker,
:write:

function subStr(_substring, _string) {
   var found =  _string.split(_substring)[0].length
   return found  <  _string.length
}
alert(subStr('ty', 'qwerty'))

devote,

function strpos(substring, string) {
    return string.split(substring).length === 2;
}
alert(strpos('привет', 'привет мир! привет'));

рони,
у меня не совсем правильный вариант, нужно не равенство ставить, а больше одного.. так как вхождений подстроки может быть больше, что-то типо:

function strpos(substring, string) {
    return string.split(substring).length > 1;
}
alert(strpos('привет', 'привет мир! привет'));

danik.js,
твой код не найдет 'lala' в 'lal111lala', т.к. выдаст false после первого неудачного захода во вложенный цикл.
devote,
да, твой второй вариант более компактный, но он найдет 'lala' в 'lal'

исправимо, совсем небольшими правками:

function strpos(substring, string) {
    var index = 0, subindex = 0;
    var subStrLen = substring.length;
    var strLen = string.length;
    while(subindex < subStrLen && index < strLen) {
        if (substring.charCodeAt(subindex) === string.charCodeAt(index)) {
            subindex++;
        } else {
            index -= subindex;
            subindex = 0;
        }
        index++;
    }
    return subindex && subindex === subStrLen;
}
alert(strpos('привет', 'привет мир!'));
alert(strpos('lala', 'lal'));

Да, так работает как надо. Всем спасибо большое)

devote,
твой код в среднем в 10 раз быстрее моего первоначального...

но только из-за использования charCodeAt

// моя фун-я
function subStr(substring, string) {
	var found = false, k = 1, sbl = substring.length, stl = string.length;
	for(var i = 0; i < stl; i++) {
		if(string.charCodeAt(i) == substring.charCodeAt(0)) {
			for(var j = 1, l = i + 1; j < sbl; j++, l++) if (string.charCodeAt(l)) {
				if(string.charCodeAt(l) == substring.charCodeAt(j)) {
					k++;
				} else {
					k = 1;
					break;
				}
			}
			if(k == sbl) {
				found = true;
				break;
			} else {
				i = l;
			}				
		}
	}
	return found;
}

// фун-я devote
function strpos(substring, string) {
    var index = 0, subindex = 0;
    var subStrLen = substring.length;
    var strLen = string.length;
    while(subindex < subStrLen && index < strLen) {
        if (substring.charCodeAt(subindex) === string.charCodeAt(index)) {
            subindex++;
        } else {
            index -= subindex;
            subindex = 0;
        }
        index++;
    }
    return subindex && subindex === subStrLen;
}


console.time('compare by char codes');
for (var i=0; i<100000; i++) strpos('друг', 'здравствуй, здравствуй, друг мордастый!');
console.timeEnd('compare by char codes');


console.time('compare by char codes2');
for (var j=0; j<100000; j++) subStr('друг', 'здравствуй, здравствуй, друг мордастый!');
console.timeEnd('compare by char codes2');

Хм, но если я применю оптимизацию с charCodeAt в своем коде, он начинает быть быстрее. Я не для пиписькомерства, просто интересно, у меня же вроде вложенный цикл есть :-?

Дзен-трансгуманист,
спасибо за разъяснение.

Хотите оптимизации, ну тогда вот ловите.. Думаю ни для кого не секрет что вычитание работает в разы быстрее сложения.

function strpos(substring, string) {
    var substringStartPos = substring.length - 1;
    var subindex = substringStartPos;
    var index = string.length - 1;
    for( ;subindex >= 0 && index >= 0; ) {
        if (substring.charCodeAt(subindex) === string.charCodeAt(index)) {
            subindex--;
        } else if (subindex !== substringStartPos) {
            index += substringStartPos - subindex;
            subindex = substringStartPos;
        }
        index--;
    }
    return substringStartPos && subindex === -1;
}

console.time('compare by char codes');
for (var i=0; i<100000; i++) strpos('друг', 'здравствуй, здравствуй, друг мордастый!');
console.timeEnd('compare by char codes');