Pagini recente » Cod sursa (job #1073347) | Cod sursa (job #1296842) | Cod sursa (job #2939058) | Cod sursa (job #2384833) | Cod sursa (job #863602)
Cod sursa(job #863602)
#include <vector>
#include <fstream>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
using namespace std;
#define LL long long
#define INFILE "strmatch.in"
#define OUTFILE "strmatch.out"
#define SMAX 2000010
#define SOLMAX 1024
ifstream fin(INFILE);
ofstream fout(OUTFILE);
string a, b;
int t[SMAX], sol[SOLMAX];
int main() {
fin >> a >> b;
int res = 0;
t[0] = -1;
int k = 0, n = a.size(), m = b.size();
for(int j=1; j<n; j++) {
while( k && a[j]!=a[k] ) k = t[k-1];
if( a[j]==a[k] ) k++;
t[j] = k;
}
k = 0;
for(int i=0; i<m; i++) {
while( k && b[i]!=a[k] ) k = t[k-1];
if( b[i]==a[k] ) k++;
if( k==n ) {
sol[res++] = i-n+1;
k = t[k-1];
}
t[i] = k;
}
fout << res << '\n';
for(int i=0; i<min(res, 1000); i++)
fout << sol[i] << " ";
return 0;
}