Pagini recente » Cod sursa (job #520817) | Cod sursa (job #1148526) | Cod sursa (job #257263) | Cod sursa (job #1811087) | Cod sursa (job #1199124)
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int MAX_LUNG = 2000000;
char a[MAX_LUNG+1], b[MAX_LUNG+1];
int prefix[MAX_LUNG+1];
int nrap = 0, k = 0, i;
int appoz[MAX_LUNG+1];
int m, n;
int main()
{
in >> (a+1) >> (b+1);
n = strlen(a+1);
m = strlen(b+1);
prefix[1] = 0;
for(i = 2; i <= n; i++)
{
while(k > 0 && a[i] != a[k+1])
{
k = prefix[k];
}
if(a[i] == a[k+1])
{
k++;
}
prefix[i] = k;
}
k = 0;
for(i = 1; i <= m; i++)
{
while(k > 0 && b[i] != a[k+1])
{
k = prefix[k];
}
if(b[i] == a[k+1])
{
k++;
}
if(k == n)
{
nrap++;
appoz[nrap] = i-n;
}
}
out << nrap << "\n";
for(i = 1; i <= nrap && i <= 1000; i++)
{
out << appoz[i] << " ";
}
in.close();
out.close();
return 0;
}