Задача: Модификация ф-ии strstr, возвращает все вхождения подстроки в строку
так, чтобы она возвращала указатель на массив, содержащий индексы всех вхождений подстроки в строку.
Пример:
строка: aaabbaaabb
подстрока: bb
результат: 3, 8
Моя реализация ниже, буду благодарен за комментарии.
Код:
#include <iostream>
using namespace std;
//добавление нового элемента в массив
void addElement(int*& ar, int el, int &N)
{
int* temp = new int [N + 1], t=0;
for(int i=0; i<N; i++)
{
temp = ar[t];
++t;
}
temp[N] = el;
++N;
delete []ar;
ar = temp;
}
//cтрока, подстрока, массив индексов, размер массива индексов
void strstr(char* str, char* sub, int*& r, int& r_size)
{
//длина подстр и исх стр, счетчик эл-тов массива индексов и указ на результат
int sub_l=0, str_l=0, rs=0, *res=0;
while(str[str_l]!='\0') str_l++; //длина исходной строки
while(sub[sub_l]!='\0') sub_l++; //длина подстроки
if(str_l == 1) return; //если 1 эл в строке
else if(sub_l == 1)//если 1 эл в подстроке
{
for(int i = 0; i<str_l; i++)
if(sub[0] == str)
addElement(res,i,rs);
r = res; //возврат массива индексов
r_size = rs; //размерность массива индексов
return;
}
for(int i=0; i<str_l; i++)
if(str==sub[0]) //если совпал символ с первым символом подстроки
{
int t = ++i, count=0;
for(int j=1; j<sub_l; j++) //ищем вхождение
{
if(str[t] == sub[j])
{
++count;
if(count == sub_l-1) //если вхождение
//выделяем ячейку и записываем индекс
addElement(res,i-1,rs);
}
++t;
}
}
r = res; //возврат массива индексов
r_size = rs; //размерность массива индексов
}
int main()
{
char str[50], sub[50];
int *r, r_size;
cout<<"String:"<<endl;
cin.getline(str,49);
cout<<"Sub string:"<<endl;
cin.getline(sub,49);
strstr(str,sub,r,r_size);
for(int i=0; i<r_size; i++) //вывод индексов
cout<<r<<endl;
delete []r;
return 0;
}
using namespace std;
//добавление нового элемента в массив
void addElement(int*& ar, int el, int &N)
{
int* temp = new int [N + 1], t=0;
for(int i=0; i<N; i++)
{
temp = ar[t];
++t;
}
temp[N] = el;
++N;
delete []ar;
ar = temp;
}
//cтрока, подстрока, массив индексов, размер массива индексов
void strstr(char* str, char* sub, int*& r, int& r_size)
{
//длина подстр и исх стр, счетчик эл-тов массива индексов и указ на результат
int sub_l=0, str_l=0, rs=0, *res=0;
while(str[str_l]!='\0') str_l++; //длина исходной строки
while(sub[sub_l]!='\0') sub_l++; //длина подстроки
if(str_l == 1) return; //если 1 эл в строке
else if(sub_l == 1)//если 1 эл в подстроке
{
for(int i = 0; i<str_l; i++)
if(sub[0] == str)
addElement(res,i,rs);
r = res; //возврат массива индексов
r_size = rs; //размерность массива индексов
return;
}
for(int i=0; i<str_l; i++)
if(str==sub[0]) //если совпал символ с первым символом подстроки
{
int t = ++i, count=0;
for(int j=1; j<sub_l; j++) //ищем вхождение
{
if(str[t] == sub[j])
{
++count;
if(count == sub_l-1) //если вхождение
//выделяем ячейку и записываем индекс
addElement(res,i-1,rs);
}
++t;
}
}
r = res; //возврат массива индексов
r_size = rs; //размерность массива индексов
}
int main()
{
char str[50], sub[50];
int *r, r_size;
cout<<"String:"<<endl;
cin.getline(str,49);
cout<<"Sub string:"<<endl;
cin.getline(sub,49);
strstr(str,sub,r,r_size);
for(int i=0; i<r_size; i++) //вывод индексов
cout<<r<<endl;
delete []r;
return 0;
}
А почему бы не использовать C++ ?
Цитата: Green
А почему бы не использовать C++ ?
Вы имеете ввиду String? Если да, то задача стоит именно в работе со строками в стиле Си.
Цитата: Stalcer
Вы имеете ввиду String? Если да, то задача стоит именно в работе со строками в стиле Си.
Я имею в виду в первую очередь алгоритмы <algorithm>.
Код:
//добавление нового элемента в массив
void addElement(int*& ar, int el, int &N)
void addElement(int*& ar, int el, int &N)
Тут вы очевидно пытаетесь "расширять" динамический массив на 1, выделя место для n+1 элемента и перенося в него n первых элементов.
НО(!)
Такая функция в языке С существует - называется:
void* reallok(void* dest, int size) - расширяет область (dest) до нужного количества(size) в байтах и возвращает указатель на область.
2.
Код:
//cтрока, подстрока, массив индексов, размер массива индексов
bool strstr(char* str, char* sub, int*& r, int& r_size)
bool strstr(char* str, char* sub, int*& r, int& r_size)
Если вы имеете r_size, то bool является лишним, так как r_size вполне достаточно: (r_size==0)~false; (r_size>0)~true;
В остальном функция довольно логично построена...
Когда то я такое же делал: :)
Вот вариант, как бы я реализовал это сегодня:
Код:
#include <iostream>
using namespace std;
#define _Out
int* strstr_arr(char* str_1, char* str_2, _Out int &count)
{
count = 0; //число нахождений
int *indexs; //масив индексов
char* _It = str_1-1; //Текущее положение
while((_It = strstr(++_It, str_2))>str_1) //До тех пора можно найти подстроку правее текущего положения приравневаем положение к найденному
*((indexs=(int*)realloc(indexs,(++count)*sizeof(int)))+count-1)=_It-str_1; //Расширяем массив, увеличиваем count, последний элемент массива кладем равным разнице между положением и началом
return indexs;
}
void main()
{
char* str = "faaabaaadf";
char* find = "aa";
int count;
int* Arr = strstr_arr(str,find,count);
for(int i=0;i<count;i++)
cout<<Arr<<endl;
free(Arr);
}
using namespace std;
#define _Out
int* strstr_arr(char* str_1, char* str_2, _Out int &count)
{
count = 0; //число нахождений
int *indexs; //масив индексов
char* _It = str_1-1; //Текущее положение
while((_It = strstr(++_It, str_2))>str_1) //До тех пора можно найти подстроку правее текущего положения приравневаем положение к найденному
*((indexs=(int*)realloc(indexs,(++count)*sizeof(int)))+count-1)=_It-str_1; //Расширяем массив, увеличиваем count, последний элемент массива кладем равным разнице между положением и началом
return indexs;
}
void main()
{
char* str = "faaabaaadf";
char* find = "aa";
int count;
int* Arr = strstr_arr(str,find,count);
for(int i=0;i<count;i++)
cout<<Arr<<endl;
free(Arr);
}
После того как r будет не нужен, его надо удалить.
В данном случае программа завершится и утечка не будет иметь значения, но лучше сразу привыкать затыкать дыры, чем потом искать их в огромном проекте :rolleyes:
Риалок не использовал в учебных целях. Сейчас буду разбирать ваш пример :)
GreenRiver, спасибо, учел :)