Pagini recente » Cod sursa (job #972918) | Cod sursa (job #827863) | Cod sursa (job #1795748) | Cod sursa (job #2297004) | Cod sursa (job #1913846)
#include <fstream>
#include <string.h>
using namespace std;
ofstream out("strmatch.out");
ifstream in("strmatch.in");
const int N_MAX = 2000000;
const int M_MAX = 2000000;
const int NumberOfPositions = 1000;
char s[1 + N_MAX + 1 + M_MAX];
int fail[1 + N_MAX + 1 + M_MAX], position[NumberOfPositions], nr;
void kmp()
{
in >> 1 + s;
int sizeA = strlen(1 + s);
s[1 + sizeA] = '$';
in >> 1 + s + sizeA + 1;
fail[0] = -1;
fail[1] = 0;
for(int i = 2; s[i] != 0; i++)
{
int j = fail[i-1] + 1;
while(j > 0 && s[i] != s[j])
j = fail[j-1] + 1;
if(j == 0) j = 1;
if(s[i] == s[j])
fail[i] = j;
else fail[i] = 0;
if(fail[i] == sizeA)
{
nr++;
if(nr<1000)
position[nr-1] = i - 2*sizeA - 1;
}
}
}
void write()
{
out << nr << "\n";
for(int i = 0; i < nr & i < 1000; i++)
out << position[i] << " ";
}
int main()
{
kmp();
write();
return 0;
}