Pagini recente » Cod sursa (job #1721789) | Cod sursa (job #2411946) | Cod sursa (job #2428869) | Cod sursa (job #1747239) | Cod sursa (job #1585592)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int STR_MAX = 2000000;
char word[STR_MAX + 5];
char str[STR_MAX + 5];
int pre[STR_MAX + 5];
void change(char s[], int len);
void prefix(char s[], int pre[], int len);
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int positions[1001];
int lenw, lens, k, ind = 0;
fin.getline(word, STR_MAX+2);
fin.getline(str, STR_MAX+2);
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';
}