Решение задачи №202 «Поиск подстроки» с ACMP
Условие задачи
Найти все вхождения строки T в строке S.
Входные данные
В первой строке входного файла INPUT.TXT записана строка S, во второй строке записана строка T. Обе строки состоят только из английских букв. Длины строк могут быть в диапазоне от 1 до 50 000 включительно.
Выходные данные
В выходной файл OUTPUT.TXT нужно вывести все вхождения строки T в строку S в порядке возрастания. Нумерация позиций строк начинается с нуля.
Решение на C++
Решение на 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