Pagini recente » preONI 2008 - Runda 2, Clasele 5-8 | Cod sursa (job #42673) | Cod sursa (job #23064) | Cod sursa (job #2960937) | Cod sursa (job #1651665)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[2000005],B[2000005];
vector <int> Sol;
int nA,nB,pi[2000005];
void make_prefix(){
int q=0;
for(int i=2;i<=nA;i++){
while(q && A[q+1]!=A[i]){
q=pi[q];
}
if(A[q+1]==A[i]){
++q;
}
pi[i]=q;
}
}
int main()
{
f>>A+1>>B+1;
nA=strlen(A+1);
nB=strlen(B+1);
make_prefix();
int q=0;
for(int i=1;i<=nB;i++){
while(q && A[q+1]!=B[i]){
q=pi[q];
}
if(A[q+1]==B[i]){
++q;
}
if(q==nA){
if(Sol.size()<1000){
Sol.push_back(i-nA);
}
}
}
g<<Sol.size()<<"\n";
for(int i=0;i<Sol.size();i++){
g<<Sol[i]<<" ";
}
return 0;
}