Pagini recente » Cod sursa (job #1594315) | Cod sursa (job #1858089) | Cod sursa (job #2362796) | Cod sursa (job #1545377) | Cod sursa (job #3147864)
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int STRLEN_MAX = 2e6;
const char SANTINELA = '&';
const int POS_MAX = 1e3;
char str[STRLEN_MAX + 2], pattern[STRLEN_MAX + 1];
int z[STRLEN_MAX];
int pos[POS_MAX];
int strlen(const char* str){
int len = 0;
while(str[len])
++len;
return len;
}
void ComputeZFunction(const char* pattern, const char* str){
int left = 0, right = 0, i = 0;
while(str[i]){
if(i <= right)
z[i] = min(z[i - left], right - i + 1);
else
z[i] = 0;
while(pattern[z[i]] == str[i + z[i]])
++z[i];
if(i + z[i] - 1 > right){
right = i + z[i] - 1;
left = i;
}
++i;
}
}
int ZAlgorithm(const char* pattern, char* str){
int pattern_len = strlen(pattern);
int str_len = strlen(str);
str[str_len] = SANTINELA;
str[str_len + 1] = '\0';
ComputeZFunction(pattern, str);
str[str_len] = '\0';
int i = 0, matches = 0;
while(str[i]){
if(z[i] == pattern_len){
if(matches < POS_MAX)
pos[matches] = i;
++matches;
}
++i;
}
return matches;
}
int main(){
fin >> pattern >> str;
int matches = ZAlgorithm(pattern, str);
fout << matches << '\n';
if(matches > POS_MAX)
matches = POS_MAX;
for(int i = 0; i < matches; ++i)
fout << pos[i] << ' ';
fout.put('\n');
fin.close();
fout.close();
return 0;
}