Pagini recente » Cod sursa (job #1582793) | Monitorul de evaluare | Istoria paginii runda/verificareoni | Cod sursa (job #2224665) | Cod sursa (job #547211)
Cod sursa(job #547211)
// http://infoarena.ro/problema/strmatch
#include <fstream>
#include <string>
using namespace std;
#define maxSize 2000002
#define maxAnswers 1002
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int matches;
int indexx[maxAnswers];
int lengthA,lengthB;
int pi[maxSize];
string A,B;
void makePrefix();
int main() {
in >> A >> B;
lengthA = A.size();
lengthB = B.size();
lengthA--;
lengthB--;
makePrefix();
//for(int i=0;i<=lengthA;i++)
//out << pi[i] << " ";
int q = 0;
for(int i=0;i<=lengthB;i++) {
while(q && A[q] != B[i])
q = pi[q];
if(A[q] == B[i])
q++;
if(q == lengthA + 1) {
q = pi[lengthA];
indexx[++matches] = i - lengthA;
}
}
out << matches << "\n";
int stop = min(matches,1000);
for(int i=1;i<=stop;i++)
out << indexx[i] << " ";
in.close();
out.close();
return (0);
}
void makePrefix() {
int q = 0;
for(int i=2;i<=lengthA;i++) {
while(q && A[q] != A[i])
q = pi[q];
if(A[q] == A[i])
q++;
pi[i] = q;
}
}