Pagini recente » Cod sursa (job #1190754) | Cod sursa (job #1140562) | Cod sursa (job #2764497) | Cod sursa (job #1448098) | Cod sursa (job #1830820)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define N 2000005
using namespace std;
struct elem
{
char sir[N];
int pattern[N];
}a;
char b[N];
vector <int> vec;
void afisare()
{
int l = vec.size();
for(int i = 0 ; i < l && i < 1000 ; ++i)
{
printf("%d ",vec[i]);
}
}
void creare()
{
int n = strlen(a.sir);
for(int i = 0 , j = 1 ; j < n ; )
{
if(a.sir[i] == a.sir[j])
{
a.pattern[j] = i + 1;
i++;
j++;
continue;
}
while(i)
{
i = a.pattern[i - 1];
if(a.sir[i] == a.sir[j])
{
a.pattern[j] = i + 1;
i++;
j++;
}
}
j++;
}
}
void comparare()
{
int m = strlen(b);
int n = strlen(a.sir);
int nr = 0;
for(int i = 0 , j = 0 ; i < m ; )
{
if(j == n)
{
nr++;
vec.push_back(i - j);
j = a.pattern[j - 1];
if(i == m - 1)
{
break;
}
}
if(a.sir[j] == b[i])
{
i++;
j++;
continue;
}
while(j)
{
j = a.pattern[j - 1];
if(a.sir[j] == b[i])
{
i++;
j++;
if(j == n)
{
nr++;
vec.push_back(i - j);
j = a.pattern[j - 1];
if(i == m - 1)
{
i++;
break;
}
}
}
}
i++;
}
printf("%d\n",nr);
afisare();
}
void citire()
{
gets(a.sir);
gets(b);
creare();
comparare();
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
citire();
return 0;
}