Pagini recente » Cod sursa (job #2029979) | Cod sursa (job #1967540) | Statistici Soarean Gabriel Alin (GabiSorean) | Monitorul de evaluare | Cod sursa (job #1585566)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
void change(char s[], int len);
void prefix(char s[], int pre[], int len);
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char word[100005];
char str[100005];
int pre[100005];
int positions[1001];
int lenw, lens, k, ind = 0;
fin.getline(word, 100000);
fin.getline(str, 100000);
lenw = strlen(word);
lens = strlen(str);
change(word, lenw);
change(str, lens);
prefix(word, pre, lenw);
k = 0;
for(int i=1; i<=lens; ++i){
while(k > 0 && str[i] != word[k+1])
k = pre[k];
if(str[i] == word[k+1])
k++;
if(k == lenw){
ind++;
if(ind <= 1000)
positions[ind] = i - lenw;
}
}
fout << ind << "\n";
for(int i=1; i<=ind && i<=1000; ++i)
fout << positions[i] << " ";
return 0;
}
void prefix(char s[], int pre[], int len){
int k = 0;
pre[1] = 0;
for(int i=2; i<=len; ++i){
while(k > 0 && s[i] != s[k+1])
k = pre[k];
if(s[i] == s[k+1])
k++;
pre[i] = k;
}
}
void change(char s[], int len){
for(int i=len; i>0; --i)
s[i] = s[i-1];
s[len+1] = '\0';
}