Pagini recente » Cod sursa (job #2674526) | Cod sursa (job #2473715) | Cod sursa (job #2203373) | Monitorul de evaluare | Cod sursa (job #2787449)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f ("a.in");
ofstream g ("a.out");
int cnt;
int rasp[2000001];
char patt[2000001],text[2000001];
int prefixe[2000001];
int lpatt,ltext;
void formare_prefixe()
{
int i = 1,j=0;
while(i<ltext)
{
if(patt[i] == patt[j])
{
prefixe[i] = j+1;
i++;
j++;
}
else
{
if(j)
{
j = prefixe[j-1];
}
else
prefixe[i++] = j;
}
}
}
void kmp()
{
int indice_secv = 0,indice_text = 0;
while(indice_text<ltext)
{
if(text[indice_text] == patt[indice_secv])
{
indice_text++;
indice_secv++;
}
else
{
if(indice_secv)
{
indice_secv = prefixe[indice_secv-1];
}
else
{
indice_text++;
}
}
if(indice_secv == lpatt)
{
rasp[cnt++] = indice_text-indice_secv;
}
}
}
int main()
{
f.getline(patt,2000000);
f.getline(text,2000000);
lpatt= strlen(patt);
ltext = strlen(text);
formare_prefixe();
kmp();
g << cnt<< endl;
for(int i = 0;i<cnt;i++)
g << rasp[i]<< " ";
}