Pagini recente » Cod sursa (job #1928664) | Cod sursa (job #3278840) | Cod sursa (job #1140614) | Cod sursa (job #163923) | Cod sursa (job #1006969)
#include <iostream>
#include <string.h>
#include <fstream>
#define STR_MAX 2000000
#define WORD_MAX 2000000
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];
ap[a++]=i-m;
}
}
}
int main()
{
in.getline(word, WORD_MAX, '\n');
in.getline(str, STR_MAX, '\n');
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();
out<<a<<endl;
for(int i=0; i<a; i++)
out<<ap[i]<<" ";
return 0;
}