Pagini recente » Cod sursa (job #2274945) | Cod sursa (job #1290596) | Cod sursa (job #1905945) | Cod sursa (job #1100021) | Cod sursa (job #2040935)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char P[2000005], T[2000005];
int main() {
fin.getline(P, 2000005);
fin.getline(T, 2000005);
int lprefix[strlen(P)],
k = 0;
lprefix[0] = 0;
for(int i = 1; i < strlen(P); ++i) {
while(k > 0 && P[i] != P[k])
k = lprefix[k-1];
if(P[i] == P[k]) k += 1;
lprefix[i] = k;
}
// for(int i = 0; i < strlen(P); ++i) {
// cout<<lprefix[i]<<' ';
// }
vector<int> aparitii;
k = 0;
for(int i = 0; i < strlen(T) && aparitii.size() < 1000; ++i) {
while(k > 0 && T[i] != P[k]) {
k = lprefix[k-1];
}
if(T[i] == P[k]) ++k;
if(k == strlen(P)) {
aparitii.push_back(i - k + 1);
k = lprefix[k-1];
}
}
fout<<aparitii.size()<<'\n';
for(vector<int> :: iterator it = aparitii.begin(); it != aparitii.end(); ++it) {
fout<<*it<<' ';
}
fin.close();
fout.close();
return 0;
}