Pagini recente » Cod sursa (job #40741) | Cod sursa (job #1140799) | Cod sursa (job #1512379) | Cod sursa (job #1922875) | Cod sursa (job #338673)
Cod sursa(job #338673)
#include <stdio.h>
#include <vector>
#include <string.h>
#define MAXN 2000002
using namespace std;
char a[MAXN],b[MAXN];
int pi[MAXN];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
vector<int> sol;
int sza,szb,i,k = -1,ss = 0;
scanf("%s",&a);
sza = strlen(a);
scanf("%s",&b);
szb = strlen(b);
pi[0] = -1;
for (i=1;i<sza;i++)
{
while (k>-1 && a[i] != a[k+1])
{
k = pi[k];
}
if (a[i] == a[k+1])
{
k++;
}
pi[i] = k;
}
k = -1;
for (i=0;i<szb;i++)
{
while (k>-1 && b[i] != a[k+1])
{
k = pi[k];
}
if (b[i] == a[k+1])
{
k++;
}
if (k == sza-1)
{
ss++;
if (sol.size() < 1000)
{
sol.push_back(i-sza+1);
}
k = pi[k];
}
}
printf("%d\n",ss);
for (i=0;i<sol.size();i++)
{
printf("%d ",sol[i]);
}
return 0;
}