Решение задачи №202 «Поиск подстроки» с ACMP

Условие задачи

Найти все вхождения строки T в строке S.

Входные данные
В первой строке входного файла INPUT.TXT записана строка S, во второй строке записана строка T. Обе строки состоят только из английских букв. Длины строк могут быть в диапазоне от 1 до 50 000 включительно.

Выходные данные
В выходной файл OUTPUT.TXT нужно вывести все вхождения строки T в строку S в порядке возрастания. Нумерация позиций строк начинается с нуля.

Решение на C++


    #include<iostream>

#include<string>

using namespace std;

int main(){

	string s,t;

	int n,m,i,j,k,d[256];

	cin>>s>>t; n=s.size(); m=t.size();

	for(i=0;i<256;++i)d[i]=m;

	for(i=0;i<m-1;++i)d[(unsigned)t[i]]=m-i-1;

	i=m-1;

	do{

		j=m-1;k=i;

			while(j>=0&&t[j]==s[k]){j--;k--;}

			if(j<0)cout<<k+1<<' ';

			i+=d[s[i]]; 

	}while(i<n);

	return 0;}

Условия задач взяты с сайта acmp.ru