Pagini recente » Cod sursa (job #2085832) | Cod sursa (job #1081300) | Cod sursa (job #1485172) | Cod sursa (job #673001) | Cod sursa (job #2979326)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char a[2000005], b[2000005];
int p[2000005], g[2000005] , r;
void Prefix()
{
int n = strlen(b+1);
int k = 0;
p[1] = 0;
for(int i = 2 ; i <= n ; ++i)
{
while(k > 0 && b[k + 1] != b[i])
k = p[k];
if(b[k + 1] == b[i])
k++;
p[i] = k;
}
}
int main()
{
fin >> (b + 1) >> (a + 1);
Prefix();
int n = strlen(a+1), m = strlen(b + 1) , k = 0;
for(int i = 1 ; i <= n ; ++i)
{
while(k > 0 && b[k + 1] != a[i])
k = p[k];
if(a[i] == b[k + 1])
k++;
if(k == m && r < 1000) k = p[m] , g[++r] = i - m;
}
fout << r << endl;
for(int i = 1 ; i <= min(r , 1000) ; ++i) fout << g[i] <<" ";
}