Pagini recente » Cod sursa (job #2046627) | Cod sursa (job #1585022) | Cod sursa (job #742033) | Cod sursa (job #688356) | Cod sursa (job #1006995)
#include <iostream>
#include <string.h>
#include <fstream>
#define STR_MAX 2000002
#define WORD_MAX 2000002
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char str[STR_MAX], word[WORD_MAX];
int L[WORD_MAX], k = 1, m, n, ap[1000], a;
void prefix()
{
L[1] = 0;
for(int i = 2; i <=m; i++)
{
k = L[i-1];
while(k > 0 && word[i] != word[k+1])
k = L[k];
if(word[i] == word[k+1])
k++;
L[i] = k;
}
}
void KMP()
{
k = 0;
for(int i = 1; i <= n; i++)
{
while(k && word[k+1] != str[i])
k = L[k];
if(word[k+1] == str[i])
k++;
if(k == strlen(word)-1)
{
k = L[k];
if(a < 1000)
ap[a++] = i-m;
}
}
}
int main()
{
in.getline(word, WORD_MAX, '\n');
in.getline(str, STR_MAX, '\n');
//cout<<word;
m = strlen(word);
n = strlen(str);
for(int i = strlen(word)+1; i >= 1; i--)
word[i] = word[i-1];
for(int i = strlen(str)+1; i >= 1; i--)
str[i] = str[i-1];
str[0] = ' ';
word[0] = ' ';
prefix();
KMP();
cout << a << '\n';
for(int i = 0; i < min(a, 1000); i++)
cout << ap[i] << " ";
return 0;
}