Pagini recente » Cod sursa (job #1068450) | Cod sursa (job #2961505) | Cod sursa (job #1547926) | Cod sursa (job #2504185) | Cod sursa (job #2335608)
///strmatch pe infoarena
#define LMAX 2000005
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s[LMAX]; /// stringul in care cautam
char p[LMAX]; /// stringul cautat
int P[LMAX]; /// Sirul cu prefixe
int fin[1005];
int n, m, o;
void formare_Prefixe()
{
int i=0, j=-1;
P[0] = -1;
while(i < m)
{
while(j >= 0 && p[i] != p[j])
j = P[j];
i++;
j++;
P[i] = j;
}
}
void kmp()
{
int i=0, j=0;
while(i < n)
{
while(j >= 0 && s[i] != p[j])
j = P[j];
i++;
j++;
if(j == m)
{
j = P[j];
if(o < 1000)
fin[o++] = i-m;
}
}
}
void afis()
{
g<<o<<'\n';
for(int i=0; i<o; i++)
g<<fin[i]<<" ";
}
int main()
{
f.getline(p, LMAX);
m = strlen(p);
f.getline(s, LMAX);
n = strlen(s);
formare_Prefixe();
kmp();
afis();
return 0;
}