Pagini recente » Cod sursa (job #1770417) | Cod sursa (job #1955799) | Cod sursa (job #2982631) | Cod sursa (job #994588) | Cod sursa (job #2709319)
#include <bits/stdc++.h>
#define ull long long
#define nmax 2000005
#define bmax 10000
#define mod 1000000007
#define ui unsigned int
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[nmax], b[nmax];
int n, m;
int urm[nmax];
vector<int>v;
void urmat(char *p)
{
int k = -1;
urm[0] = 0;
for(int x = 1; x < m; x++)
{
while(k > 0 && p[k + 1] != p[x])
k = urm[k];
if(p[k + 1] == p[x])
k++;
urm[x] = k;
}
}
int main()
{
int x = -1, cnt = 0;
f >> b;
f >> a;
n = strlen(a);
m = strlen(b);
urmat(b);
/* for(int i = 1; i < m; i++)
cout << urm[i] << " ";*/
for(int i = 0; i < n; i++)
{
while(x > 0 && b[x + 1] != a[i])
x = urm[x];
if(b[x + 1] == a[i])
x++;
if(x == m - 1)
{
cnt++;
if(cnt <= 1000)
v.push_back(i - m + 1);
//cout << i - m + 1 << ' ';
x = urm[x];
}
}
if(cnt <= 1000)
g << cnt << '\n';
else
g << 1000 << '\n';
for(int i = 0; i< v.size(); i++)
g << v[i] << " ";
return 0;
}