Pagini recente » Cod sursa (job #1821707) | Cod sursa (job #1192996) | Cod sursa (job #616149) | Cod sursa (job #1054961) | Cod sursa (job #1072609)
#include <cstdio>
#include <string>
#define MAXN 2000003
using namespace std;
char word[MAXN], text[MAXN];
int fi_word[MAXN], fi_text[MAXN], result[1002], count = 0;
void read() {
freopen( "strmatch.in", "r", stdin );
freopen( "strmatch.out", "w", stdout );
scanf("%s", word);
scanf("%s", text);
}
int getLength(char *c) {
int len = 0;
while( *c != '\0') {
c++;
len++;
}
return len;
}
void compute_word() {
fi_word[0] = -1;
int length = getLength(word);
int q;
for(int k = 1; k < length; k++) {
q = fi_word[k-1];
while( q != -1 && word[k] != word[q + 1] )
q = fi_word[q];
if( word[k] == word[q + 1] )
q++;
fi_word[k] = q;
}
}
void solve() {
int length_text = getLength(text);
int length_word = getLength(word);
int k = -1;
for(int i = 0; i < length_text; i++) {
while( k != -1 && text[i] != word[k + 1])
k = fi_word[k];
if( text[i] == word[k+1] )
k++;
if ( k == length_word - 1) {
count++;
if (count < 1001)
result[count] = i + 1 - length_word;
}
}
}
void print() {
printf("%i\n", count);
int min = count < 1001 ? count : 1000;
for(int i = 1; i <= min; i++)
printf("%i ", result[i]);
}
int main() {
read();
compute_word();
solve();
print();
return 0;
}