Pagini recente » Cod sursa (job #1455882) | Cod sursa (job #322924) | Cod sursa (job #877226) | Cod sursa (job #2233185) | Cod sursa (job #1228557)
using namespace std;
#include <fstream>
#define Lgmax 2000002
int p[Lgmax], sol[Lgmax], nrSol = 0;
char a[Lgmax], b[Lgmax];
void read() ;
int preprocess(char*, int*) ;
void write() ;
int main()
{
int i, k, m;
read();
m = preprocess(a, p);
for(i = 1, k = 0; b[i] != '\0'; ++i)
{
while(k > 0 && b[i] != a[k + 1])
k = p[k];
if(b[i] == a[k + 1]) ++k;
if(k == m) sol[++nrSol] = i - m;
}
write();
return 0;
}
void read()
{
ifstream fin("strmatch.in");
fin.getline(a + 1, Lgmax);
fin.getline(b + 1, Lgmax);
fin.close();
}
int preprocess(char s[], int v[])
{
int k, q;
v[0] = v[1] = 0;
for(q = 2, k = 0; s[q] != '\0'; ++q)
{
while(k > 0 && s[q] != s[k + 1]) k = v[k];
if(s[q] == s[k + 1]) ++k;
v[q] = k;
}
return q - 1;
}
void write()
{
ofstream fout("strmatch.out");
fout << nrSol << '\n';
nrSol = min(nrSol, 1000);
for(int i = 1; i <= nrSol; ++i)
fout << sol[i] << ' ';
fout << '\n';
fout.close();
}