Pagini recente » Cod sursa (job #599879) | Cod sursa (job #1473483) | Cod sursa (job #2181037) | Cod sursa (job #1081251) | Cod sursa (job #2979313)
#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), 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 == strlen(b+1) && r < 1000) g[++r] = i - strlen(b+1);
}
fout << r << endl;
for(int i = 1 ; i <= r ; ++i) fout << g[i] <<" ";
}